代码随想录学习笔记——动态规划之滚动数组: Leetcode63. 不同路径 II
之前面试被问到动态规划是什么，其实在读研期间是学过的，但是两年来对算法的逻辑接触几乎是0，没答上来，也算吸取教训，查漏补缺。跟着Leetcode的动态规划（基础版）学习计划过过题，在遇到第63题的时候看题解注意到一个滚动数组法，有点意思，记录一下。
题目描述
63. 不同路径Ⅱ
63. 不同路径Ⅱ
https://leetcode.cn/problems/unique-paths-ii/description/
给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。
网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
返回机器人能够到达右下角的不同路径数量。测试用例保证答案小于等于 2 * 109。
解题方法
熟悉动态规划的话这道题我感觉会很容易，从结尾往回倒推，对于位置为(i, j)的位置，如果其元素为1，则无法抵达。而机器人只能向下或向右移动，那么状态转移方程也久比较好列了：
和官方题解的逻辑不太一样，为了统一理解，这里的ob(i,j)代表（i，j）处是否右障碍物，如果有障碍物，那么代表这个位置无法抵达，如果没有，那么机器人可以从该点的上方（向下运动）或者左侧（向右运动）抵达。
只是需要注意几种特殊的情况，或者说动态规划问题中的初始状态。
- 起点是障碍物：不用想，直接返回0；
- 输入矩阵是一个行向量：遍历这个行向量，如果都是0（无障碍），那么返回1；
- 输入矩阵是一个列向量：遍历这个列向量，如果都是0（无障碍），那么返回1；
第二种和第三种情况看似很接近，但这里就需要注意行和列的选择 一定要认真，我就是因为自己定义的height和width没有整明白导致耽误了好久。
解题代码如下，若可改进欢迎指正/
class Solution {public: int uniquePathsWithObstacles(vector<vector>& obstacleGrid) { int height = obstacleGrid.size(); int width = obstacleGrid[0].size(); vector<vector> states(height, vector(width, 0)); for (int i = 0; i < height; i++){ if (obstacleGrid[i][0] == 1){ break; } states[i][0] = 1; } for (int i = 0; i < width; i++){ if (obstacleGrid[0][i] == 1){ break; } states[0][i] = 1; } for(int i = 1; i < height; i++){ for (int j = 1; j < width; j++){ if(obstacleGrid[i][j] == 0 ){ states[i][j] = states[i-1][j]+states[i][j-1]; } } } return states[height-1][width-1]; }};滚动数组
分析官方的解法，其核心思想在于该问题场景下位置变化的无后效性，也就是任何大于当前i和j的状态f\'和当前的f(i，j)均无关。这样一来可以把原先的二维动态规划问题压缩成一维的针对列的求解。具体而言，我们观察之前的状态转移方程：
i和j都会发生改变，因此在空间上复杂度就会使O(mn)。与之相比，在滚动数组法，我们只定义一个一维的数组f[j] 表示到达当前行第 j 列格子的路径总数；在遍历新行前，f[j] 存储的是上一行第 j 列的值（即从上方来的路径数）；在遍历当前行时，f[j] 会被更新为当前行第 j 列的值。此时状态转移也会发生变化，
-
路径数 = 上方来的路径数（存储在
f[j]中） + 左边来的路径数（存储在f[j-1]中）
当格子上有障碍的时候直接设置f[j] = 0 ，也就是不可达。 官方解法代码如下：
class Solution {public: int uniquePathsWithObstacles(vector<vector>& obstacleGrid) { int n = obstacleGrid.size(), m = obstacleGrid.at(0).size(); vector f(m); // 滚动数组，大小为列数m // 初始化起点 f[0] = (obstacleGrid[0][0] == 0); // 起点无障碍=1，有障碍=0 for (int i = 0; i < n; ++i) { for (int j = 0; j = 0 && obstacleGrid[i][j - 1] == 0) { f[j] += f[j - 1]; } } } return f.back(); // 返回右下角格子的路径数 }};滚动数组举个栗子
0 0 00 1 00 0 0就拿这个栗子来说，1代表障碍物，现在机器人要从左上角运动到右下角。
1. 首先进行初始化，f = [1, 0, 0]，也就是说起点没有障碍，从起点运动到起点只有一条路径。
2. 接着进入循环，开始i=0的循环，即处理第一行。
-
j=0：无障碍 → 保持
f[0]=1（不执行加法） -
j=1：无障碍 → 执行
f[1] += f[0]→0+1=1 -
j=2：无障碍 → 执行
f[2] += f[1]→0+1=1 -
结果：
f = [1, 1, 1]
3. 接着第二行 ：
-
j=0：无障碍 → 保持
f[0]=1（从上方来） -
j=1：有障碍 → 设置
f[1]=0 -
j=2：无障碍 → 但左边格子（i=1,j=1）是障碍 → 不执行加法 → 保持
f[2]=1（从上方来） -
结果：
f = [1, 0, 1]
4. 第三行：
-
j=0：无障碍 → 保持
f[0]=1 -
j=1：无障碍 → 执行
f[1] += f[0]→0+1=1 -
j=2：无障碍 → 执行
f[2] += f[1]→1+1=2 -
结果：
f = [1, 1, 2]
最后一步返回f.back() = 2
