[LeetCode]动态规划及LeetCode题解分析

动态规划（DP，Dynamic programming）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。给定一个问题，如果可以将其划分为子问题，并解出其子问题，再根据子问题的解推导/递推以得出原问题的解。

上述描述也许使得动态规划听起来像递归，但动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。

☆ START ☆

1

解题思路：三大步骤

前述已经提到，动态规划是利用子问题的解推导出原问题的解，即用之前问题的解推导出之后问题的解，即利用已有的解（历史保存的解）来解未知的问题。那么我们需要用什么数据结构来保存已有的解（历史记录）呢？一般来说是数组，有一维的，更多情况下会使用二维的。

总结而言，动态规划解题包括三大步骤：

（1）明确数组元素代表的含义

针对具体问题，声明了一个数组，那么这个数组每个元素代表什么含义？假设使用一维数组dp，那么每一项dp[i]代表什么意思？如果使用二维数组dp，那么每一项dp[i][j]代表什么含义？这是首先需要明确的。

（2）寻找递推关系，务必考虑特殊情况下的递推关系

以一维数组为例，明确了dp[i]的含义了，那么dp[i]和dp[i+1]是什么关系？可以通过怎样的关系式将二者关联起来？找到了这个递推关系，就可以知道任意i的时候的值。

特殊情况是指的什么呢？比如存在边界条件，或者题目要求的某个范围，或者题目有特殊说明等，这是需要额外注意的。

这一步是动态规划的关键！

（3）数组初始化

还是以一维数组为例，每一项dp[i]的含义明确了，dp[i]与dp[i+1]的关系式也找到了，总得有个最初的值吧，即dp[0]，有的时候由于0,1的特殊性，初始值甚至包括dp[1]，dp[2]等。

2

LeetCode题解分析

LeetCode上关于动态规划的题目很多，目前（2019/12）分类里有176道。这里结合上述三大步骤，详解3道题。

01

[LeetCode.62]不同路径

https://leetcode-cn.com/problems/unique-paths/

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？ 说明：m 和 n 的值均不超过 100。

示例 1: 输入: m = 3, n = 2 输出: 3 解释: 从左上角开始，总共有 3 条路径可以到达右下角。1. 向右 -> 向右 -> 向下 2. 向右 -> 向下 -> 向右 3. 向下 -> 向右 -> 向右 示例 2: 输入: m = 7, n = 3 输出: 28

这里我们使用二维数组dp[][]。根据前述的三大步骤：

（1）明确数组含义

dp[i][j]代表什么？——机器人走到网格(i,j)总共有多少种路径。

（2）寻找递推关系

题目中明确告诉“机器人每次只能向下或者向右移动一步”，因此，机器人走到(i,j)，有可能是从(i-1,j)向下走，也可能是从(i,j-1)向右走一步。也就是说，dp[i][j]=dp[i-1][j]+dp[i][j-1].

这里有没有特殊情况呢？显然有的，那就是机器人位于网格边界时（网格上面第一横排和左边第一竖排），上述递推关系需要修改：

• 当机器人位于网格第一横排时，i=0，dp[0][j]只能从dp[0][j-1]向右移动一步得到，即dp[0][j] = dp[0][j-1]；
• 当机器人位于网格第一竖排时，j=0，dp[i][0]只能从dp[i-1][0]向下移动一步得到，即dp[i][0] = dp[i-1][0]；

（3）数组初始化

机器人最初位于网格左上角，dp[0][0]是唯一开始点，所以dp[0][0] = 1.

（4）Code

int uniquePaths(int m, int n) {
        int **dp;
        dp = new int*[m];
        for(int i=0;i<m;i++){
            dp[i] = new int[n];
        }

        dp[0][0] = 1;

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0&&j==0){
                    continue;
                }
                else if(i==0){
                    dp[i][j] = dp[i][j-1];
                }
                else if(j==0){
                    dp[i][j] = dp[i-1][j];
                }
                else{
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }

01

[LeetCode.63]不同路径II

https://leetcode-cn.com/problems/unique-paths-ii/

该题与上一题的区别在于，网格中有障碍物。

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。 说明：m 和 n 均不超过 100。 示例 1: 输入: [ [0,0,0], [0,1,0], [0,0,0] ] 输出: 2 解释: 从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

同样我们使用二维数组dp[][]。类似于第62题，根据前述的三大步骤：

（1）明确数组含义

dp[i][j]——机器人走到网格(i,j)总共有多少种路径。

（2）寻找递推关系

通式：dp[i][j]=dp[i-1][j]+dp[i][j-1].

特殊情况有两种，一方面是边界条件：

• 当机器人位于网格第一横排时，i=0，dp[0][j]只能从dp[0][j-1]向右移动一步得到，即dp[0][j] = dp[0][j-1]；
• 当机器人位于网格第一竖排时，j=0，dp[i][0]只能从dp[i-1][0]向下移动一步得到，即dp[i][0] = dp[i-1][0]；

另一方面则是题目中所述的障碍物，即网格中值为1的格子是机器人不能达的。那么在通式dp[i][j]=dp[i-1][j]+dp[i][j-1]的基础上，对于网格(i,j)：

• 如果(i-1,j)中有障碍物，那么dp[i][j]=dp[i][j-1]；
• 同理，如果(i,j-1)中有障碍物，那么dp[i][j]=dp[i-1][j]；

（3）数组初始化

机器人最初位于网格左上角，dp[0][0]是开始点，所以dp[0][0] = 1.

（4）Code

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        long m = obstacleGrid.size();
        long n = obstacleGrid[0].size();
        long **dp = new long*[m];
        for(long i=0;i<m;i++){
            dp[i] = new long[n];
        }
        // 初始化
        for(long i=0;i<m;i++){
            for(long j=0;j<n;j++){
                dp[i][j] = obstacleGrid[i][j]==1?0:1;
            }
        }
        for(long i=0;i<m;i++){
            for(long j=0;j<n;j++){
                if(i==0&j==0){
                    if(obstacleGrid[i][j]==1){
                        dp[0][0] = 0;
                    }
                    continue;
                }
                else if(obstacleGrid[i][j]==1){
                    continue;
                }
                else if(i==0){
                    dp[i][j] = dp[i][j-1];
                }
                else if(j==0){
                    dp[i][j] = dp[i-1][j];
                }
                else{
                    dp[i][j] = ((obstacleGrid[i-1][j]==1?0:dp[i-1][j]))+
                    ((obstacleGrid[i][j-1]==1?0:dp[i][j-1]));
                }
            }
        }
        return obstacleGrid[m-1][n-1]==1?0:dp[m-1][n-1];
    }

01

[LeetCode.64]最小路径和

https://leetcode-cn.com/problems/minimum-path-sum/

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。 示例: 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。

这道题其实也是个最短路径问题，那么同样，我们使用二维数组。

（1）明确数组含义

dp[i][j]——走到网格(i,j)时的最短路径值（包括该网格的路径值）。

（2）寻找递推关系

题目限制条件是“每次只能向下或者向右移动一步”，那么(i,j)只能从(i-1,j)和(i,j-1)移动到达，而要求最短路径，就是在比较dp[i-1][j]和dp[i][j-1]的值大小，取其小。即通式：dp[i][j]=min(dp[i-1][j], dp[i][j-1])+grid[i][j].

特殊情况是边界条件：

• 当机器人位于网格第一横排时，i=0，dp[0][j]只能从dp[0][j-1]向右移动一步得到，即dp[0][j] = dp[0][j-1]；
• 当机器人位于网格第一竖排时，j=0，dp[i][0]只能从dp[i-1][0]向下移动一步得到，即dp[i][0] = dp[i-1][0]；

另一方面则是题目中所述的障碍物，即网格中值为1的格子是机器人不能达的。那么在通式dp[i][j]=dp[i-1][j]+dp[i][j-1]的基础上，对于网格(i,j)：

• 如果(i-1,j)中有障碍物，那么dp[i][j]=dp[i][j-1]；
• 同理，如果(i,j-1)中有障碍物，那么dp[i][j]=dp[i-1][j]；

（3）数组初始化

机器人最初位于网格左上角，(0,0)是唯一开始点，所以dp[0][0] = grid[0][0].

（4）Code：其实可以不必新声明数组，直接使用原有的即可

int minPathSum(vector<vector<int>>& grid) {
        int i=0,j=0;
        for( i = 0;i<grid.size();i++){
            for( j=0;j<grid[0].size();j++){
                if(i==0 && j==0){
                    continue;
                }
                else if(i==0){
                    grid[i][j]+=grid[i][j-1];
                }
                else if(j==0){
                    grid[i][j]+=grid[i-1][j];
                }
                else{
                    grid[i][j] = grid[i][j]+(grid[i][j-1]<grid[i-1][j]?grid[i][j-1]:grid[i-1][j]);
                }
            }
        }
        return grid[grid.size()-1][grid[0].size()-1];
    }