class Solution {
public:
int numberOfWays(int startPos, int endPos, int k) {
}
};
2400. 恰好移动 k 步到达某一位置的方法数目
给你两个 正 整数 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原站题解
java 解法, 执行用时: 19 ms, 内存消耗: 50.6 MB, 提交时间: 2023-06-17 09:19:14
class Solution {
int MOD = (int) 1e9 + 7;
int[][] memo;
public int numberOfWays(int startPos, int endPos, int k) {
/*
记忆化DFS
1 <= startPos, endPos, k <= 1000
设向左的步数为l，向右的步数为r，走到终点等价于 r-l=endPos-startPos
其中l+r=k && 0<=l<=k && 0<=r<=k && l与r均为整数
可得知方程只有唯一解:l=(k+startPos-endPos)/2，r=(k+endPos-startPos)/2
若有一个不是整数可以直接返回0，若都为整数通过记忆化dfs求解
时间复杂度:O(k^2) 空间复杂度:O(k^2)
*/
memo = new int[k + 1][k + 1];
int ll = k + startPos - endPos, rr = k + endPos - startPos;
// 先判断绝对不可能到达||不能凑成到达终点的情况
if (endPos - startPos > k || ll % 2 == 1 || rr % 2 == 1) return 0;
return dfs(ll / 2, rr / 2);
}
// 计算当向左移动次数为l，向右移动次数为r时的方案数(取余后)
private int dfs(int l, int r) {
if (memo[l][r] != 0) return memo[l][r];
// base case -> 当某一边用完了，剩下的只有1种方案
if (l == 0 || r == 0) return 1;
// 当前的选择可以是向左或者向右
int res = (dfs(l - 1, r) + dfs(l, r - 1)) % MOD;
memo[l][r] = res; // 记录
return res;
}
}
golang 解法, 执行用时: 328 ms, 内存消耗: 55.8 MB, 提交时间: 2023-06-17 09:18:09
func numberOfWays(startPos, endPos, k int) int {
type pair struct{ x, y int }
dp := map[pair]int{}
var f func(int, int) int
f = func(x, left int) int {
if abs(x-endPos) > left {
return 0
}
if left == 0 {
return 1 // 成功到达终点，算一种方案
}
p := pair{x, left}
if v, ok := dp[p]; ok {
return v
}
res := (f(x-1, left-1) + f(x+1, left-1)) % (1e9 + 7)
dp[p] = res
return res
}
return f(startPos, k)
}
func abs(x int) int { if x < 0 { return -x }; return x }
python3 解法, 执行用时: 964 ms, 内存消耗: 298.6 MB, 提交时间: 2023-06-17 09:17:54
# 定义 f(x,left) 表示当前在 x，还剩 left 步时，走到终点的方案数。
# 枚举下一步往左或者往右，累加即为答案
class Solution:
def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
MOD = 10 ** 9 + 7
@cache
def f(x: int, left: int) -> int:
if abs(x - endPos) > left: return 0
if left == 0: return 1 # 成功到达终点，算一种方案
return (f(x - 1, left - 1) + f(x + 1, left - 1)) % MOD
return f(startPos, k)
cpp 解法, 执行用时: 4 ms, 内存消耗: 6.2 MB, 提交时间: 2023-06-17 09:16:57
class Solution {
const int MOD = 1000000007;
public:
int numberOfWays(int startPos, int endPos, int K) {
int d = abs(startPos - endPos);
if ((d + K) % 2 == 1 || d > K) return 0;
// 线性求逆元
vector<long long> inv(K + 1);
inv[1] = 1;
for (int i = 2; i <= K; i++) inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
// 递推求组合数，初值 C(k, 0) = 1
long long ans = 1;
for (int i = 1; i <= (d + K) / 2; i++) ans = ans * (K - i + 1) % MOD * inv[i] % MOD;
return ans;
}
};
cpp 解法, 执行用时: 56 ms, 内存消耗: 73.8 MB, 提交时间: 2023-06-17 09:16:48
class Solution {
const int MOD = 1000000007;
public:
int numberOfWays(int startPos, int endPos, int K) {
int d = abs(startPos - endPos);
if ((d + K) % 2 == 1 || d > K) return 0;
// 递推求组合数
vector<vector<long long>> f;
f.resize(K + 1, vector<long long>(K + 1));
for (int i = 0; i <= K; i++) {
f[i][0] = 1;
for (int j = 1; j <= i; j++) f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % MOD;
}
return f[K][(d + K) / 2];
}
};