题目描述
给你有一个 非负 整数 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 开始。
- 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 。
提示：
解法
方法一：记忆化搜索
我们设计一个函数 $\textit{dfs}(i, j, \textit{jump})$，表示当前位于第 $i$ 级台阶，且进行了 $j$ 次操作 $1$ 和 $\textit{jump}$ 次操作 $2$，到达第 $k$ 级台阶的方案数。那么答案就是 $\textit{dfs}(1, 0, 0)$。
函数 $\textit{dfs}(i, j, \textit{jump})$ 的计算过程如下：
- 如果 $i > k + 1$，由于无法连续两次向下走，所以无法再到达第 $k$ 级台阶，返回 $0$；
- 如果 $i = k$，表示已经到达第 $k$ 级台阶，答案初始化为 $1$，然后继续计算；
- 如果 $i > 0$ 且 $j = 0$，表示可以向下走，递归计算 $\textit{dfs}(i - 1, 1, \textit{jump})$；
- 递归计算 $\textit{dfs}(i + 2^{\textit{jump}}, 0, \textit{jump} + 1)$，累加到答案中。
为了避免重复计算，我们使用记忆化搜索，将已经计算过的状态保存起来。
时间复杂度 $(\log ^2 k)$，空间复杂度 $(\log ^2 k)$。
1
2
3
4
5
6
7
8
9
10
11
12
13 | class Solution:
def waysToReachStair(self, k: int) -> int:
@cache
def dfs(i: int, j: int, jump: int) -> int:
if i > k + 1:
return 0
ans = int(i == k)
if i > 0 and j == 0:
ans += dfs(i - 1, 1, jump)
ans += dfs(i + (1 << jump), 0, jump + 1)
return ans
return dfs(1, 0, 0)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | class Solution {
private Map<Long, Integer> f = new HashMap<>();
private int k;
public int waysToReachStair(int k) {
this.k = k;
return dfs(1, 0, 0);
}
private int dfs(int i, int j, int jump) {
if (i > k + 1) {
return 0;
}
long key = ((long) i << 32) | jump << 1 | j;
if (f.containsKey(key)) {
return f.get(key);
}
int ans = i == k ? 1 : 0;
if (i > 0 && j == 0) {
ans += dfs(i - 1, 1, jump);
}
ans += dfs(i + (1 << jump), 0, jump + 1);
f.put(key, ans);
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution {
public:
int waysToReachStair(int k) {
unordered_map<long long, int> f;
auto dfs = [&](this auto&& dfs, int i, int j, int jump) -> int {
if (i > k + 1) {
return 0;
}
long long key = ((long long) i << 32) | jump << 1 | j;
if (f.contains(key)) {
return f[key];
}
int ans = i == k ? 1 : 0;
if (i > 0 && j == 0) {
ans += dfs(i - 1, 1, jump);
}
ans += dfs(i + (1 << jump), 0, jump + 1);
f[key] = ans;
return ans;
};
return dfs(1, 0, 0);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | func waysToReachStair(k int) int {
f := map[int]int{}
var dfs func(i, j, jump int) int
dfs = func(i, j, jump int) int {
if i > k+1 {
return 0
}
key := (i << 32) | jump<<1 | j
if v, has := f[key]; has {
return v
}
ans := 0
if i == k {
ans++
}
if i > 0 && j == 0 {
ans += dfs(i-1, 1, jump)
}
ans += dfs(i+(1<<jump), 0, jump+1)
f[key] = ans
return ans
}
return dfs(1, 0, 0)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | function waysToReachStair(k: number): number {
const f: Map<bigint, number> = new Map();
const dfs = (i: number, j: number, jump: number): number => {
if (i > k + 1) {
return 0;
}
const key: bigint = (BigInt(i) << BigInt(32)) | BigInt(jump << 1) | BigInt(j);
if (f.has(key)) {
return f.get(key)!;
}
let ans: number = 0;
if (i === k) {
ans++;
}
if (i > 0 && j === 0) {
ans += dfs(i - 1, 1, jump);
}
ans += dfs(i + (1 << jump), 0, jump + 1);
f.set(key, ans);
return ans;
};
return dfs(1, 0, 0);
}
|