题目描述
给你两个 正 整数 startPos 和 endPos 。最初，你站在 无限 数轴上位置 startPos 处。在一步移动中，你可以向左或者向右移动一个位置。
给你一个正整数 k ，返回从 startPos 出发、恰好 移动 k 步并到达 endPos 的 不同 方法数目。由于答案可能会很大，返回对 109 + 7 取余 的结果。
如果所执行移动的顺序不完全相同，则认为两种方法不同。
注意：数轴包含负整数。
示例 1：
输入：startPos = 1, endPos = 2, k = 3
输出：3
解释：存在 3 种从 1 到 2 且恰好移动 3 步的方法：
- 1 -> 2 -> 3 -> 2.
- 1 -> 2 -> 1 -> 2.
- 1 -> 0 -> 1 -> 2.
可以证明不存在其他方法，所以返回 3 。
示例 2：
输入：startPos = 2, endPos = 5, k = 10
输出：0
解释：不存在从 2 到 5 且恰好移动 10 步的方法。
提示：
1 <= startPos, endPos, k <= 1000
解法
方法一：记忆化搜索
我们设计一个函数 $dfs(i, j)$，表示当前位置距离目标位置的距离为 $i$，还剩 $j$ 步，有多少种方法到达目标位置。那么答案就是 $dfs(abs(startPos - endPos), k)$。
函数 $dfs(i, j)$ 的计算方式如下：
- 如果 $i \gt j$ 或者 $j \lt 0$，说明当前位置距离目标位置的距离大于剩余步数，或者剩余步数为负数，此时无法到达目标位置，返回 $0$；
- 如果 $j = 0$，说明剩余步数为 $0$，此时只有当前位置距离目标位置的距离为 $0$ 时才能到达目标位置，否则无法到达目标位置，返回 $1$ 或者 $0$；
- 否则，当前位置距离目标位置的距离为 $i$，还剩 $j$ 步，那么有两种方法到达目标位置：
- 向左移动一步，此时当前位置距离目标位置的距离为 $i + 1$，还剩 $j - 1$ 步，方法数为 $dfs(i + 1, j - 1)$；
- 向右移动一步，此时当前位置距离目标位置的距离为 $abs(i - 1)$，还剩 $j - 1$ 步，方法数为 $dfs(abs(i - 1), j - 1)$；
- 最后，返回两种方法的和对 $10^9 + 7$ 取余的结果。
为了避免重复计算，我们使用记忆化搜索，即使用一个二维数组 $f$ 记录函数 $dfs(i, j)$ 的结果，当函数 $dfs(i, j)$ 被调用时，如果 $f[i][j]$ 不为 $-1$，则直接返回 $f[i][j]$，否则计算 $f[i][j]$ 的值，并返回 $f[i][j]$。
时间复杂度 $O(k^2)$，空间复杂度 $O(k^2)$。其中 $k$ 为题目给定的步数。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
@cache
def dfs(i: int, j: int) -> int:
if i > j or j < 0:
return 0
if j == 0:
return 1 if i == 0 else 0
return (dfs(i + 1, j - 1) + dfs(abs(i - 1), j - 1)) % mod
mod = 10**9 + 7
return dfs(abs(startPos - endPos), k)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution {
private Integer[][] f;
private final int mod = (int) 1e9 + 7;
public int numberOfWays(int startPos, int endPos, int k) {
f = new Integer[k + 1][k + 1];
return dfs(Math.abs(startPos - endPos), k);
}
private int dfs(int i, int j) {
if (i > j || j < 0) {
return 0;
}
if (j == 0) {
return i == 0 ? 1 : 0;
}
if (f[i][j] != null) {
return f[i][j];
}
int ans = dfs(i + 1, j - 1) + dfs(Math.abs(i - 1), j - 1);
ans %= mod;
return f[i][j] = ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public:
int numberOfWays(int startPos, int endPos, int k) {
const int mod = 1e9 + 7;
int f[k + 1][k + 1];
memset(f, -1, sizeof(f));
function<int(int, int)> dfs = [&](int i, int j) -> int {
if (i > j || j < 0) {
return 0;
}
if (j == 0) {
return i == 0 ? 1 : 0;
}
if (f[i][j] != -1) {
return f[i][j];
}
f[i][j] = (dfs(i + 1, j - 1) + dfs(abs(i - 1), j - 1)) % mod;
return f[i][j];
};
return dfs(abs(startPos - endPos), k);
}
};
|
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
30
31
32
33
34
35 | func numberOfWays(startPos int, endPos int, k int) int {
const mod = 1e9 + 7
f := make([][]int, k+1)
for i := range f {
f[i] = make([]int, k+1)
for j := range f[i] {
f[i][j] = -1
}
}
var dfs func(i, j int) int
dfs = func(i, j int) int {
if i > j || j < 0 {
return 0
}
if j == 0 {
if i == 0 {
return 1
}
return 0
}
if f[i][j] != -1 {
return f[i][j]
}
f[i][j] = (dfs(i+1, j-1) + dfs(abs(i-1), j-1)) % mod
return f[i][j]
}
return dfs(abs(startPos-endPos), k)
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | function numberOfWays(startPos: number, endPos: number, k: number): number {
const mod = 10 ** 9 + 7;
const f = new Array(k + 1).fill(0).map(() => new Array(k + 1).fill(-1));
const dfs = (i: number, j: number): number => {
if (i > j || j < 0) {
return 0;
}
if (j === 0) {
return i === 0 ? 1 : 0;
}
if (f[i][j] !== -1) {
return f[i][j];
}
f[i][j] = dfs(i + 1, j - 1) + dfs(Math.abs(i - 1), j - 1);
f[i][j] %= mod;
return f[i][j];
};
return dfs(Math.abs(startPos - endPos), k);
}
|