停在原地的方案数Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
有一个长度为 arrLen 的数组，开始有一个指针在索引 0 处。
每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。
给你两个整数 steps 和 arrLen ，请你计算并返回：在恰好执行 steps 次操作以后，指针仍然指向索引 0 处的方案数。
由于答案可能会很大，请返回方案数 模 10^9 + 7 后的结果。
示例 1：
输入：steps = 3, arrLen = 2
输出：4
解释：3 步后，总共有 4 种不同的方法可以停在索引 0 处。
向右，向左，不动
不动，向右，向左
向右，不动，向左
不动，不动，不动
示例 2：
输入：steps = 2, arrLen = 4
输出：2
解释：2 步后，总共有 2 种不同的方法可以停在索引 0 处。
向右，向左
不动，不动
示例 3：
输入：steps = 4, arrLen = 2
输出：8
提示：
- 1 <= steps <= 500
- 1 <= arrLen <= 106
# 思路
dp[i][j] 表示 执行 i 次操作后，恰好位于位置 j 的方案数
# 解法
class Solution {
private static final int k = 1000_000_007;
public int numWays(int steps, int arrLen) {
// dp[i][j] 表示 执行 i 次操作后，恰好位于位置 j 的方案数
int maxPos = Math.min(arrLen-1, steps/2); // 走太远没用
int[] dp = new int[maxPos+1];
dp[0] = 1;
// 转移方程 dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]
for(int i=1; i<=steps; i++){
int pre = 0; // dp[i-1][j-1]
for(int j=0, limit=Math.min(i, maxPos); j<=limit; j++){ // 极端情况 一直向右走
int cur = dp[j]; // dp[i-1][j]
dp[j] = (pre + dp[j]) % k;
if(j < limit){
dp[j] = (dp[j] + dp[j+1]) % k;
}
pre = cur;
}
}
return dp[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
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
# 总结
- 分析出几种情况，然后分别对各个情况实现
