题目：
给你有一个 非负 整数 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
记忆化搜索
思路：
寻找子问题
在跳台阶的过程中：
为了判断是否到达终点 k，我们需要知道当前在第几个台阶。
为了计算操作二能往上跳多少个台阶，我们需要知道已经使用了多少次操作二。
为了判断能否使用操作一（往下跳），我们需要知道上一次操作是否使用了操作一。
例如现在在第 5 个台阶，且之前使用了 3 次操作二，那么可以：
使用操作二：向上跳 2^3 = 8 个台阶，到达第 5 + 8 = 13 个台阶。接下来要解决的问题是：在使用了 4 次操作二，且上一次操作没有使用操作一的情况下，从 13 跳到 k 的方案数。
使用操作一（前提是上一次操作没有使用操作一）：向下跳 1 个台阶，到达第 5 − 1 = 4 个台阶。接下来要解决的问题是：在使用了 3 次操作二，且上一次操作使用了操作一的情况下，从 4 跳到 k 的方案数。
这些问题都是和原问题相似的子问题，可以用递归解决。
状态定义
根据上面的讨论，我们需要在递归过程中跟踪以下信息：
i：当前位于第 i 个台阶。
j：已经使用了 j 次操作二。
preDown：一个布尔值，表示上一次操作是否使用了操作一。
因此，定义状态为 dfs(i, j, preDown)，表示在使用了 j 次操作二，且上一次操作使用/未使用操作一的情况下，从 i 跳到 k 的方案数。
状态转移方程
枚举当前使用哪个操作：
使用操作二：接下来要解决的问题是 dfs(i + 2^j, j + 1, false)，将其方案数加到返回值中。
使用操作一（前提是 preDown = false 且 i > 0）：接下来要解决的问题是 dfs(i − 1, j, true)，将其方案数加到返回值中。
此外，如果 i=k（到达终点），则找到了一个方案，把返回值加一。
注意：到达第 k 个台阶后，还可以继续操作，重新回到第 k 个台阶。所以 i = k 并不是递归边界。
递归边界：如果 i > k + 1，由于操作一不能连续使用，无法到达 k，返回 0。
递归入口：dfs(1, 0, false)，即答案。一开始在第 1 个台阶，没有使用过操作二，也没有使用过操作一。
代码：
class Solution {
public:
int waysToReachStair(int k) {
unordered_map<long long, int> memo;
auto dfs = [&](auto&& dfs, int i, int j, bool pre_down) -> int {
if (i > k + 1) { // 无法到达终点 k
return 0;
}
// 把状态 (i, j, pre_down) 压缩成一个 long long
long long mask = (long long) i << 32 | j << 1 | pre_down;
if (memo.contains(mask)) { // 之前算过了
return memo[mask];
}
int res = i == k;
res += dfs(dfs, i + (1 << j), j + 1, false); // 操作二
if (i && !pre_down) {
res += dfs(dfs, i - 1, j, true); // 操作一
}
return memo[mask] = res; // 记忆化
};
return dfs(dfs, 1, 0, false);
}
};
组合数学
思路：
假设使用了 m 次操作一，j 次操作二，那么有 1 + 2^0 + 2^1 + 2^2 + ⋯ + 2^j−1 − m = k
即 m = 2^j − k 注意上式当 j=0 时也是成立的。
由于操作一不能连续使用，我们需要在这 j 次操作二前后，以及相邻两次操作二的空隙中，插入 m 个操作一，所以方案数等于从 j+1 个物品中选出 m 个物品的方案数，即 C(j + 1, m)
枚举 j，最终答案为∑(j = 0, 29) C(j + 1, m)
其中 0 ≤ m ≤ j + 1。根据题目的数据范围，j 至多枚举到 29。
代码：
int c[31][31];
auto init = [] {
for (int i = 0; i < 31; i++) {
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; j++) {
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}
}
return 0;
}();
class Solution {
public:
int waysToReachStair(int k) {
int ans = 0;
for (int j = 0; j < 30; j++) {
int m = (1 << j) - k;
if (0 <= m && m <= j + 1) {
ans += c[j + 1][m];
}
}
return ans;
}
};