题目描述
这是 LeetCode 上的 1269. 停在原地的方案数 ，难度为 困难。
Tag : 「线性 DP」
有一个长度为 arrLen 的数组，开始有一个指针在索引 0 处。
每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。
给你两个整数 steps 和 arrLen ，请你计算并返回：在恰好执行 steps 次操作以后，指针仍然指向索引 0 处的方案数。
由于答案可能会很大，请返回方案数 模 10910^9109 + 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 <= 10610^6106
动态规划
这道题的可变维度分析不算复杂，因此这次就不从 DFS 开始给大家分析了。
定义 f[i][j]f[i][j]f[i][j] 代表当前剩余操作数为 iii，所在位置为 jjj 的所有方案数。
起始位置为 000，操作次数为 stepstepstep，即有初始化条件 f[step][0]=1f[step][0] = 1f[step][0]=1，f[0][0]f[0][0]f[0][0] 则是我们的最终答案。
不失一般性的考虑 f[i][j]f[i][j]f[i][j] 可以由哪些状态转移而来：
- 由「原地」操作到达当前状态，消耗一次操作，此时由状态 f[i+1][j]f[i + 1][j]f[i+1][j] 转移而来
- 由「向左」操作到达当前状态，消耗一次操作，此时由状态 f[i+1][j+1]f[i + 1][j + 1]f[i+1][j+1] 转移而来
- 由「向右」操作到达当前状态，消耗一次操作，此时由状态 f[i+1][j−1]f[i + 1][j - 1]f[i+1][j−1] 转移而来
求的是方案数，即最终的 f[i][j]f[i][j]f[i][j] 为三者累加值。
同时我们发现 f[i][x]f[i][x]f[i][x] 依赖于 f[i+1][y]f[i + 1][y]f[i+1][y]，因此我们需要按照「stepstepstep 从大到小」的顺序进行转移。
同时我们根据「最终回到下标 000 位置」可以推断出，最远到达的位置为 step/2step / 2step/2（再远就回不来了）。将最远到达位置与数组最大下标取 minminmin 即可确定维度 stepstepstep 的范围。
代码：
class Solution { int mod = (int)1e9+7; public int numWays(int steps, int len) { int max = Math.min(steps / 2, len - 1); int[][] f = new int[steps + 1][max + 1]; f[steps][0] = 1; for (int i = steps - 1; i >= 0; i--) { for (int j = 0; j <= max; j++) { f[i][j] = (f[i][j] + f[i + 1][j]) % mod; if (j - 1 >= 0) f[i][j] = (f[i][j] + f[i + 1][j - 1]) % mod; if (j + 1 <= max) f[i][j] = (f[i][j] + f[i + 1][j + 1]) % mod; } } return f[0][0]; } } 复制代码
- 时间复杂度：共有数量级为 step∗maxstep * maxstep∗max 个的状态需要被转移。复杂度为 O(step∗max)O(step * max)O(step∗max)
- 空间复杂度：O(step∗max)O(step * max)O(step∗max)
优化
1. 对时间复杂度进行「常数级别的优化」
f[0][0]f[0][0]f[0][0] 并不依赖于操作次数同为 000 的其他位置的状态，而只依赖于操作次数为 111 的特定位置的状态。同理其他状态也是。
因此我们会发现随着「可操作次数」的减少，「可达到的最远位置」下标也会逐步缩小。从目标状态 f[0][0]f[0][0]f[0][0] 进行倒推的话，会发现「可达到的最远位置」等于「可操作次数」。
所以其实可以从两者取一个 minminmin 就能够有效减少「无效状态」的计算。数据量越大，这个性质带来的剪枝效果越好。
PS. 为了方便你看到优化前后的差别，我增加了打印注释，使用测试数据 (500, 100000) 并打开注释，可以看到少计算了多少「无效状态」。
代码：
class Solution { int mod = (int)1e9+7; public int numWays(int steps, int len) { int max = Math.min(steps / 2, len - 1); int[][] f = new int[steps + 1][max + 1]; f[steps][0] = 1; for (int i = steps - 1; i >= 0; i--) { int edge = Math.min(i, max); // if (edge != max) System.out.println(edge + " " + max); for (int j = 0; j <= edge; j++) { f[i][j] = (f[i][j] + f[i + 1][j]) % mod; if (j - 1 >= 0) f[i][j] = (f[i][j] + f[i + 1][j - 1]) % mod; if (j + 1 <= max) f[i][j] = (f[i][j] + f[i + 1][j + 1]) % mod; } } return f[0][0]; } } 复制代码
- 时间复杂度：共有数量级为 step∗maxstep * maxstep∗max 个的状态需要被转移。复杂度为 O(step∗max)O(step * max)O(step∗max)
- 空间复杂度：O(step∗max)O(step * max)O(step∗max)
2. 对空间复杂度进行「维度级别的优化」
这个优化思维难度就要低很多了，利用 f[i][x]f[i][x]f[i][x] 依赖于 f[i+1][y]f[i + 1][y]f[i+1][y]，使用「滚动数组」方式进行优化即可。
代码：
class Solution { int mod = (int)1e9+7; public int numWays(int steps, int len) { int max = Math.min(steps / 2, len - 1); int[][] f = new int[2][max + 1]; f[steps&1][0] = 1; for (int i = steps - 1; i >= 0; i--) { int edge = Math.min(i, max); int a = i & 1, b = (i + 1) & 1; for (int j = 0; j <= edge; j++) { f[a][j] = 0; f[a][j] = (f[a][j] + f[b][j]) % mod; if (j - 1 >= 0) f[a][j] = (f[a][j] + f[b][j - 1]) % mod; if (j + 1 <= max) f[a][j] = (f[a][j] + f[b][j + 1]) % mod; } } return f[0][0]; } } 复制代码
- 时间复杂度：共有数量级为 step∗maxstep * maxstep∗max 个的状态需要被转移。复杂度为 O(step∗max)O(step * max)O(step∗max)
- 空间复杂度：O(max)O(max)O(max)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1269 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
