1269. 停在原地的方案数
题目
有一个长度为 arrLen 的数组，开始有一个指针在索引 0 处。
每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。
给你两个整数 steps 和 arrLen ，请你计算并返回：在恰好执行 steps 次操作以后，指针仍然指向索引 0 处的方案数。
由于答案可能会很大，请返回方案数 模 10^9 + 7 后的结果。
示例 1：
输入：steps = 3, arrLen = 2
输出：4
解释：3 步后，总共有 4 种不同的方法可以停在索引 0 处。
向右，向左，不动
不动，向右，向左
向右，不动，向左
不动，不动，不动
提示：
1 <= steps <= 5001 <= arrLen <= 10^6
思路
这题的话不算太难，思路理清楚基本上还是可以做出来的。总共就三种状态转移方式，左移右移和不动，然后分三种情况：最左边最右边和中间的就行了。难的感觉反而还是时间和空间上的优化吧。空间优化的话就不展开了，新建数组或变量保存原来的值就可以了，就是会麻烦点。
上代码！
代码
static final int M = 1000000007;public int numWays(int steps, int arrLen) {
// 最远只能移动到steps/2,再远就回不到原点了;// 取两者最小值即可（arrLen要-1，因为len代表数组下标最末尾的值）int len = Math.min(steps / 2, arrLen - 1);// dp[i][j]表示一共i步下经过j的位置返回0有多少种移动方案（好像有点难理解哈= =）int[][] dp = new int[steps + 1][len + 1];// 初值为1dp[0][0] = 1;for (int i = 1; i <= steps; i++) {
// 枚举步数// 因为最远也只能走i步,所以取两者最小值可以减少j的循环次数（时间优化）// 不能取i/2,因为后续状态转移会用到走i步的值int x = Math.min(i, len);// 不进行优化的话j<=len即可for (int j = 0; j <= x; j++) {
// 在0处只能从右边或原地移动过来if (j == 0) {
dp[i][j] = (dp[i - 1][j] + dp[i - 1][j + 1]) % M;} else if (j == len) {
// 最右边只能从左边或原地过来（注意是len,即数组最末尾）dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % M;} else {
// 正常转移，可以从左边、右边或原地移动过来(加一次取余一次，不然数据会超限)dp[i][j] = ((dp[i - 1][j - 1] + dp[i - 1][j]) % M + dp[i - 1][j + 1]) % M;}}}return dp[steps][0];
}