摘要

• 从到达当前状态的有几种可能来思考，是一种确定dp数组及数组下标含义的方式

• 滚动数组是一种能够在动态规划中降低空间复杂度的方法，当我们在使用递推方程计算下一步状态的时候，可能只需要用到之前几个状态的数据而不是全部的数据。在这种情况下，我们就可以对推导下一步状态没用的数据进行覆盖。

LeetCode62 不同路径

62. 不同路径 - 力扣（Leetcode）

• 确定dp数组及数组下标的含义：dp[i][j]为到达第i行第j列的可能路径数。
• 确定递推方程，先考虑简单的子问题：
  1. 只有“向右走”可以到达第一行（i=0）的格子，因为第一行的上面没有格子，没有“向下走”到达第一行的格子的可能。
  2. 只有“向下走”可以到达第一列（j=0）的格子，因为第一列的左边没有格子，没有“向右走”到达第一列的格子的可能。
  3. 对于第一行或第一列以外的格子，到达第i行第j列的格子，只有两种可能，一是从第i-1行第j列的格子向下走一格，二是从第i行第j-1列的格子向右走一格。

• 由递推方程，可以得到dp数组的初始状态，即i=0的格子和j=0的格子的dp值都初始化为1。

• 确定遍历方法，在本题中，“向下走”和“向右走”都是更趋近终点的走法，所以先向下还是先向右应该是一样的，本题先遍历i还是先遍历j只是先更新行还是先更新列的区别。

题解代码如下

class Solution {
public:
    int uniquePaths(int m, int n) {
        // dp数组初始化
        vector<vector<int>> dp(m, vector<int>(n));
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 1;
        
        // 构造dp数组
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        
        // 返回结果，注意是左闭右开区间，终点对应的下标为(m-1, n-1)
        return dp[m - 1][n - 1];
    }
};

• 本题可以用滚动数组的思想进行优化
  • 滚动数组是一种能够在动态规划中降低空间复杂度的方法，在一些特殊情况下，二维动态规划方程甚至可以直接降阶到一维，是一种极为巧妙的思想。
  • 如果把dp数组看作一个表格，滚动数组可以理解为dp数组中的滑动窗口。
  • 当我们在使用递推方程计算下一步状态的时候，可能只需要用到之前几个状态的数据而不是全部的数据。在这种情况下，我们就可以对推导下一步状态没用的数据进行覆盖。
• 回顾我们之前推出的递推公式。显然，对的计算并不需要知道之前所有格子各自的路径数，只需要知道和
• 那如何体现在代码上呢？我们先来看原来的二维的dp数组是如何计算出答案的：

二维dp数组的构造过程

1. 先初始化

2. 然后，从dp[1][1]开始，逐行（或逐列）计算dp[i][j]的值，由dp[i-1][j]和dp[i][j-1]相加得到。

3. 最终得到终点的可能路径数，此时dp数组如下

滚动数组dp的构造过程

• 那么滚动数组是如何只用一维数组来计算出到达终点的可能路径数的呢？在使用二维的dp数组时，我们依然是逐行（或逐列）构造的。那么是否可以只用一行来保存计算下一状态所需的信息呢？在本题当然是可行的，我是用滑动窗口的方式理解的。

• 还是在之前那张代表二维dp数组的表格上看，青蓝色的格子代表当前dp数组保存的值。

1. 初始化dp数组

2. 接下来我们要逐行向下滑动这个窗口，怎么滑动呢？我先滑动第一个格子，第2行第1列的格子当然只能由起点向下走一格到达，所以值为1，这是自然的，为了“推出”这个值，dp[0]应该初始化为1。

   • 这与二维dp数组dp[0][0]的初始化是不同的，其实可以看出，除了m=1; n=1的情况，二维dp数组中的dp[0][0]初始化成什么值都不会影响得到正确的结果，因为当m>1; n>1时，根本没有哪一个格子的计算会用到dp[0][0]。

   • 可以拿以下代码验证上述说法

   • class Solution {
     public:
         int uniquePaths(int m, int n) {
             vector<vector<int>> dp(m, vector<int>(n));
             for (int i = 0; i < m; i++) dp[i][0] = 1;
             for (int j = 0; j < n; j++) dp[0][j] = 1;
     
             if (m != 1 || n != 1) {
                 srand(time(0));
                 dp[0][0] = rand();
             }
     
             for (int i = 1; i < m; i++) {
                 for (int j = 1; j < n; j++) {
                     dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                 }
             }
                 
             return dp[m - 1][n - 1];
         }
     };
     

3. 回到正题，明确dp[0]要初始化成1，我们由dp[0]推出了“新的”dp[0]，表现为滑动了窗口的第一个格子，将窗口的第一个格子向下滑动了一格。接下来应该滑动第二个格子，其实到这里就可以看出所谓“滚动数组”是怎么节省空间的了，”新的“dp[0]正好可以和“旧的”dp[1]加算出“新的”dp[1]

4. 这之后的dp[i]当然也是同理，所谓“滚动数组”，就是用“新的”dp[i-1]和“旧的”dp[i]计算出“新的”dp[i]，然后i++重复这一操作。滑动窗口并不是整行整行的滑动的，而是一个格子一个格子轮流向下滑动的。如果把[0-6]画成一个轮子：轮子底部滚动到哪个下标，就更新哪个下标，这或许是一种形象地理解滚动数组的方法。下图是滚动到1

5. 然后把”轮子”滚完一圈到6，就将“滑动窗口”滑动了一行

6. 再重复“轮子”的滚动，“轮子”滚动到0，之后的过程就不赘述啦

• 根据“滚动数组”，我们可以这样定义dp数组：从第一行（第一行下标为0）开始逐行向下走，dp[j]为到达当前行第j列的格子的可能路径，dp[j]的更新次数即为对应的格子所在的行的下标（下标从0开始）。

据此，不难写出如下题解代码

class Solution {
public:
    int uniquePaths(int m, int n) {
        // dp数组初始化
        vector<int> dp(n, 1);
        
        // 注意滑动窗口初始时就在第一行（下标为0的行）了
        // 所以第一次更新 dp 数组对应的应该是第二行（下标为1的行），i初始化为1
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // dp[0]是一直等于1的，不用显式的更新，从dp[1]开始更新即可
                dp[j] += dp[j - 1];
            }
        }
        //  最终 dp 数组的最后一个值即为答案
        return dp[n - 1];
    }
};

LeetCode63 不同路径II

63. 不同路径 II - 力扣（Leetcode）

• 这道题目和上一题是连着的，只是在dp数组初始化和构造的过程中加上了条件判断，对应题目提到的障碍物。还是先从直观且容易理解的二维dp数组开始

• 确定dp数组及数组下标的含义：dp[i][j]为到达第i行第j列的可能路径数。

• 确定递推方程，先考虑简单的子问题：

  1. 只有“向右走”可以到达第一行（i=0）的格子，因为第一行的上面没有格子，没有“向下走”到达第一行的格子的可能。如果第一行的某个格子出现障碍物，那么这个格子及其右边的格子都是不可到达的。设第一行中第oj列的格字出现障碍物，只有列下标小于最小的oj的格子是可以到达的。
  2. 只有“向下走”可以到达第一列（j=0）的格子，因为第一列的左边没有格子，没有“向右走”到达第一列的格子的可能。如果第一列的某个格子出现障碍物，那么这个格子及其下面的格子都是不可到达的。设第一列中第oi列的格字出现障碍物，只有行下标小于最小的oi的格子是可以到达的。
  3. 对于第一行或第一列以外的格子，到达第i行第j列的格子，只有两种可能，一是从第i-1行第j列的格子向下走一格，二是从第i行第j-1列的格子向右走一格。
  4. 如果第i行第j列的格子有障碍物，说明这个格子是不可到达，到达该格子的可能路径数是0。
  • 递推公式如下，偷懒就不用数学语言描述第一行或第一列不可到达的情况了

  

  • 也可以将乘进表达式中，来简化递推公式的条件判断，这在代码实现中也可以起到简化的作用，不用写if语句即可完成判断。

  

• 根据递推公式来初始化dp数组，在这里可以先做一次判断，如果起点或者终点有障碍物，就不需要计算了，起点或终点有障碍物时的可能路径数都是0。

• 遍历方法也和上题没有什么区别，先行后列或先列后行都可以

题解代码如下

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> dp(m, vector<int>(n));
        if (obstacleGrid[0][0] || obstacleGrid[m - 1][n - 1]) return 0;
        for (int j = 0; j < n && !obstacleGrid[0][j]; j++) dp[0][j] = 1;
        for (int i = 0; i < m && !obstacleGrid[i][0]; i++) dp[i][0] = 1;

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = !obstacleGrid[i][j] * (dp[i - 1][j] + dp[i][j - 1]);
            }
        }

        return dp[m - 1][n - 1];
    }
};

• 这道题目也可以用一维dp数组来解决，但要注意递推公式到实现代码的变化。改变dp数组的定义，一般都会引起递推公式的变化。
• 一维dp数组的定义：从第一行（第一行下标为0）开始逐行向下走，dp[j]为到达当前行第j列的格子的可能路径，dp[j]的更新次数即为对应的格子所在的行的下标（下标从0开始），如果对应的格子有障碍物，说明这个格子无法到达，可能路径数为0。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        if (obstacleGrid[0][0] || obstacleGrid[m - 1][n - 1]) return 0;
        vector<int> dp(n);
        // 根据第1行初始化滚动数组
        for (int j = 0; j < n && !obstacleGrid[0][j]; j++) {
            dp[j] = 1;
        }

        for (int i = 1; i < m; i++) {// 从第2行开始初始化滚动数组
            for (int j = 0; j < n; j++) {
                //由于第1列也可能有障碍物，dp[0]是需要我们来控制如何更新的
                if (obstacleGrid[i][j])
                    dp[j] = 0;
                else if (j > 0)// 可以到达且不为第1列的格子
                    dp[j] = dp[j] + dp[j-1];
            }
        }

        return dp.back();
    }
};