有一个长度为 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 <= 10^6
定义状态：f[i][j] 表示经过i步操作又回到下标j的方案数
状态转移方程：f[i][j] = f[i - 1][j - 1] + f[i - 1][j] + f[i - 1][j + 1]
初始状态：f[0][0] = 1，其余f[0][i] = 0(1 <= i < n)，这里要特别注意
1 class Solution { 2 public int numWays(int steps, int arrLen) { 3 int mod = 1000000000 + 7; 4 // 走的最远的下标是通过steps和arrLen共同决定的 5 int maxIndex = Math.min(steps, arrLen - 1); 6 // 优化前 7 int[][] f = new int[steps + 1][maxIndex + 1]; 8 for (int i = 0; i <= steps; i++) { 9 for (int j = 0; j <= maxIndex; j++) { 10 if (i == 0 && j == 0) { 11 f[i][j] = 1; 12 continue; 13 } 14 if (i == 0) { 15 f[i][j] = 0; 16 continue; 17 } 18 f[i][j] += f[i - 1][j]; 19 f[i][j] %= mod; 20 if (j > 0) { 21 f[i][j] += f[i - 1][j - 1]; 22 f[i][j] %= mod; 23 } 24 if (j < maxIndex) { 25 f[i][j] += f[i - 1][j + 1]; 26 f[i][j] %= mod; 27 } 28 } 29 } 30 31 return f[steps][0]; 32 }
1 class Solution { 2 public int numWays(int steps, int arrLen) { 3 int mod = 1000000000 + 7; 4 // 走的最远的下标是通过steps和arrLen共同决定的 5 int maxIndex = Math.min(steps, arrLen - 1); 6 // 优化后 7 int[][] f = new int[2][maxIndex + 1]; 8 int old = 0; 9 int now = 1; 10 for (int i = 0; i <= steps; i++) { 11 old = now; 12 now = 1 - now; 13 for (int j = maxIndex; j >= 0; j--) { 14 if (i == 0 && j == 0) { 15 f[now][j] = 1; 16 continue; 17 } 18 if (i == 0) { 19 f[now][j] = 0; 20 continue; 21 } 22 f[now][j] = f[old][j]; 23 f[now][j] %= mod; 24 if (j > 0) { 25 f[now][j] += f[old][j - 1]; 26 f[now][j] %= mod; 27 } 28 if (j < maxIndex) { 29 f[now][j] += f[old][j + 1]; 30 f[now][j] %= mod; 31 } 32 } 33 } 34 35 return f[now][0]; 36 } 37 }
Leetcode每日一题——1269. 停在原地的方案数（路径DP）
原文：https://www.cnblogs.com/pengsay/p/14769645.html