给你有一个 非负 整数 k 。有一个无限长度的台阶，最低 一层编号为 0 。
Alice 有一个整数 jump ，一开始值为 0 。Alice 从台阶 1 开始，可以使用 任意 次操作，目标是到达第 k 级台阶。假设 Alice 位于台阶 i ，一次 操作 中，Alice 可以：
- 向下走一级到
i - 1，但该操作 不能 连续使用，如果在台阶第 0 级也不能使用。 - 向上走到台阶
i + 2jump处，然后jump变为jump + 1。
请你返回 Alice 到达台阶 k 处的总方案数。
注意，Alice 可能到达台阶 k 处后，通过一些操作重新回到台阶 k 处，这视为不同的方案。
示例 1：
输入：k = 0
输出：2
解释：
2 种到达台阶 0 的方案为：
- Alice 从台阶 1 开始。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
- Alice 从台阶 1 开始。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
- 执行第二种操作，向上走 20 级台阶到台阶 1 。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
示例 2：
输入：k = 1
输出：4
解释：
4 种到达台阶 1 的方案为：
- Alice 从台阶 1 开始，已经到达台阶 1 。
- Alice 从台阶 1 开始。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
- 执行第二种操作，向上走 20 级台阶到台阶 1 。
- Alice 从台阶 1 开始。
- 执行第二种操作，向上走 20 级台阶到台阶 2 。
- 执行第一种操作，向下走 1 级台阶到台阶 1 。
- Alice 从台阶 1 开始。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
- 执行第二种操作，向上走 20 级台阶到台阶 1 。
- 执行第一种操作，向下走 1 级台阶到台阶 0 。
- 执行第二种操作，向上走 21 级台阶到台阶 2 。
- 执行第一种操作，向下走 1 级台阶到台阶 1 。
提示：
0 <= k <= 109
第一种思路：
每走一步之后，新的子问题跟原问题相比，规模更小且类型相同，因此可以用 DFS 进行递归处理。
递归的结束条件是，当 i 比 k + 1大时，终止搜索。这是再往后必不可能到达 k。
剩下的就是按照提议翻译即可，注意用两个参数记录上一步有没有往下走， 以及跳了几次。
时间复杂度：O（log(k) * log(k))
空间复杂度：O（log(k) * log(k))
class Solution:
def waysToReachStair(self, k: int) -> int:
@cache
def dfs(i, last_step_down, jump):
res = 0
if i > k + 1:
return 0
if i == k:
res = 1
if not last_step_down:
res += dfs(i - 1, True, jump)
res += dfs(i + 2 ** jump, False, jump + 1)
return res
return dfs(1, False, 0)第二种思路：
其实这道题也还可以从数学的角度进行分析，但是难度较大，没有准备过基本不可能在面试中凭空想出来。
已知我们一开始从 1 出发，可以进行 i 次减 1 操作，以及 j 次 jump 操作，最后需要到达 k。
可得：1（起点） + (2^0 + 2^1 + .. + 2^(j - 1)) - i = k
即 2^j - i = k
题目另有一个要求，是说 i 不能连续使用，即 i 必须穿插在 j 之间。
如果我们有 j 次 jump，那么就会有 j + 1 个空挡可以插入 i。
所以对于每一组(i, j) 来说，它们会形成的答案就是 Combination(j + 1, i）。
class Solution:
def waysToReachStair(self, k: int) -> int:
# 1 + 2^0 + 2^1 + .. + 2^(j - 1) - i = k
# i <= j + 1
res = 0
for j in range(30): # 2 ^ 30 > 10 ^ 9
i = 2 ** j - k
if 0 <= i <= j + 1:
res += comb(j + 1, i)
return res时间复杂度：O（1）
空间复杂度：O（1）
标签：第一种,台阶,Python,Alice,DFS,jump,3154,操作,执行 From： https://blog.csdn.net/qq_32424059/article/details/141355469