【动态规划篇】- 路径问题

62. 不同路径

题目链接： 62. 不同路径

题目解析：

1. 状态表示 dp[i][j]表示：以[i][j]为终点时，一共有多少种路径。
2. 状态转移方程 以[i][j]最近的几步来分析问题，要么从[i-1][j]位置向下走一步到达[i][j],要么从[i][j-1]向右走一步到达[i][j]。 所以dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
3. 初始化 为了防止越界，我们就需要初始化下图中红色线画的这部分

这里我们有个小技巧，那就是让dp表多开一行和一列

因为到达[1][1]这个位置共有一种路径，所以我们仅需将dp[1][0]或者dp[0][1]位置初始化为1，其余位置初始化为0即可。

1. 填表顺序 从上向下，从左向右
2. 返回值 因为dp[i][j]表示到达[i][j]位置时，一共的路径数，我们最终要到达[m][n]位置，所以我们返回dp[m][n]即可。

代码实现：

class Solution {
public:
    int uniquePaths(int m, int n) {
        //1.创建dp表
        //2.初始化
        //3.填表
        //4.返回结果
        vector<vector<int>> dp(m + 1,vector<int>(n + 1));
        dp[1][0] = 1;
        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][n];
    }
};

时间复杂度：O(m*n) 空间复杂度：O(m*n)

63. 不同路径II

题目链接： 63. 不同路径II

题目解析： 这道题和上面那道题极度的相似，只不过是加了个障碍物

1. 状态表示 dp[i][j]表示：以[i][j]为终点时，一共有多少种路径。
2. 状态转移方程 以距离[i][j]最近的一步来划分问题，划分为[i][j]上一步有障碍物时和没有障碍物时。当有障碍物时那么此时的路径就到达不了[i][j]，所以到达[i][j]的总的方法数就为0，当没有障碍物时，此时的问题就和上面那道题的思路就一摸一样了要么从[i-1][j]位置向下走一步到达[i][j],要么从[i][j-1]向右走一步到达[i][j]。所以dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。
3. 初始化 因为到达[1][1]这个位置共有一种路径，所以我们仅需将dp[1][0]或者dp[0][1]位置初始化为1，其余位置初始化为0即可。
4. 填表顺序 从上向下，从左向右
5. 返回值 因为dp[i][j]表示到达[i][j]位置时，一共的路径数，我们最终要到达[m][n]位置，所以我们返回dp[m][n]即可。

代码实现：

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& ob) {
        //1. 创建dp表   
        //2. 初始化
        //3. 填表
        //4. 返回结果
        int m = ob.size(),n = ob[0].size();
        vector<vector<int>> dp(m + 1,vector<int> (n + 1));
        dp[0][1] = 1;
        for(int i = 1;i <= m;i++)
            for(int j = 1;j <= n;j++)
                if(ob[i - 1][j - 1] == 0) //这里需要特别注意一下下标的映射关系
                     dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

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

时间复杂度：O(m*n) 空间复杂度：O(m*n)

LCR 166. 珠宝的最高价值

题目链接： LCR 166. 珠宝的最高价值

题目解析：

1. 状态表示 dp[i][j]表示：以[i][j]为终点时，获得的珠宝的最高价值
2. 状态转移方程 以最近的一步来划分问题，要么从[i-1][j]位置走一步到达[i][j],要么从[i-1][j]位置走一步到达[i][j]，此时珠宝的最高价值就是dp[i-1][j]和dp[i][j-1]两者大的一个加上[i][j]位置珠宝的价值。所以dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + frame[i][j]，这里要注意下标的映射关系，所以此时的frame[i][j]应该是frame[i-1][j-1]，因为数组整体向右下角移动了一位。
3. 初始化 这道题我们申请dp表时也多开出一行和一列，为了不影响其余位置的值，我们将这一行和这一列初始化成0即可。
4. 填表顺序 从上往下，自左向右
5. 返回值 因为dp[i][j]表示以[i][j]为终点时，获得的珠宝的最高价值，我们最终要到达右下角，记二维数组的宽为m宽为n，所以返回dp[m][n]

代码实现：

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m = frame.size(),n = frame[0].size();
        //1.创建dp表
        vector<vector<int>> dp(m + 1 ,vector<int> (n + 1));
        //2.初始化
        //因为vector创建的数组默认初始化为0，所以这里不用做处理
        //3.填表
        for(int i = 1;i <= m;i++)
            for(int j = 1;j <= n;j++)
                dp[i][j] = max(dp[i][j-1],dp[i-1][j]) + frame[i-1][j-1];
        return dp[m][n];
    }
};

时间复杂度：O(m*n) 空间复杂度：O(m*n)

931. 下降路径最小和

题目链接： 931. 下降路径最小和

题目解析：

1. 状态表示 dp[i][j]表示：到达[i][j]位置时的最小下降路径
2. 状态转移方程 以最近的一步来划分问题

要到达[i][j]位置，要么从1位置到达[i][j],要么从2位置到达[i][j],要么从3位置到达[i][j]

dp[i][j] = min(dp[i-1][j-1],min(do[i-1][j],dp[i-1][j+1])) + matrix[i][j]

1. 初始化 为了保证填表的时候不越界，所以我们在创建dp表的时候多开一行，多开两列。 为了保证虚拟节点里面的值不影响填表，所以我们在初始化的时候将dp表里面的值都初始化为+∞，将第一行初始化为0即可。

1. 填表顺序 从上往下
2. 返回值 由于最后要求的是下降路径的和最小，dp[i][j]表示的是到达[i][j]位置时的和最小，所以我们返回最后一行的最小值即可

代码实现：

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        //1.创建dp表
        int n = matrix.size();
        vector<vector<int>> dp(n+1,vector<int>(n + 2,INT_MAX));
        //2.初始化
        for(int i = 0;i <= n;i++) dp[0][i] = 0;
        //3.填表
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
                dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1])) + matrix[i-1][j-1];

        int ret = INT_MAX;
        for(int i = 0;i <= n;i++) ret = min(ret,dp[n][i]);
        return ret;
                
    }
};

时间复杂度：O(n²) 空间复杂度：O(n²)

64. 最小路径和

题目链接： 64. 最小路径和

题目解析：

1. 状态表示 dp[i][j]表示：到达[i][j]位置时的数字最小和
2. 状态转移方程 以最近的一步来分析问题，到达[i][j]位置，要么从[i][j-1]位置向右走一步到达[i][j],要么从[i-1][j]位置向下走一步到达[i][j]。要求到达[i][j]位置数字最小和只需求得到达[i][j-1]位置数字最小和在加上[i][j]位置上的数字与[i-1][j]位置数字最小和在加上[i][j]位置上的数字的小的那一个。 所以dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + grid[i][j] 🔖这里应注意下标的映射关系，因为下面初始化时我们多开了一行和一列，相当于网格整体向右下角挪了一位，所以最后加的应是grid[i-1][j-1]
3. 初始化 下图蓝色圆圈标出的地方会用到绿色方框处的值，此时会产生越界，为了防止越界，所以我们创建dp表的时候多开一行和一列

因为我们要求的是上边和左边小的那一个，所以我们在初始化dp表的时候初始化为+∞,将dp[0][1]或者dp[1][0]初始化为0即可

1. 填表顺序 从上往下，从左往右
2. 返回值 因为要求的是到达终点时路径上的数字的和最小，dp[i][j]表示到达[i][j]位置是的数字最小值，最后返回最后位置的值即可

代码实现：

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        //1.创建dp表
        int m = grid.size(),n = grid[0].size();
        vector<vector<int>> dp(m + 1,vector<int> (n + 1));
        //2.初始化
        for(int i = 2;i <= n ;i++) dp[0][i] = INT_MAX;
        for(int j = 2;j <= m ;j++) dp[j][0] = INT_MAX;
        //3.填表
        for(int i = 1;i <= m;i++)
            for(int j = 1;j <= n;j++)
                dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i-1][j-1];
        
        return dp[m][n];
    }
};

时间复杂度：O(m*n) 空间复杂度：O(m*n)

174. 地下城游戏

题目链接： 174. 地下城游戏

题目解析：

1. 状态表示 我们的状态表示方法有两种 ①以某个位置为结尾 ②以某个位置为起点 这道题当我们尝试以某个位置为结尾考虑问题的时候，我们会发现我们还需要知道这个位置的下一个值，那么以某个位置为结尾来表示这道题是不行的。 所以我们就以[i][j]位置为起点定义状态表示 dp[i][j]表示：以[i][j]位置为起点到达终点时，所需要的最低初始健康点数
2. 状态转移方程 我们以[i][j]位置为起点，必须满足dp[i][j]+dungeon[i][j]≥1，然后要么向右走一步，要么向下走一步，向右走一步必须满足dp[i][j]+dungeon[i][j]≥dp[i][j+1]，向下走一步必须满足dp[i][j]+dungeon[i][j]≥dp[i+1][j],所以dp[i][j]≥dp[i][j+1]-dungeon[i][j] 或者dp[i][j]≥dp[i+1][j]-dungeon[i][j] ，因为要求的是dp[i][j]的最小值，最后取等即可 ,由于要求的是到达终点时的最低健康点数，所以我们最后取两者中小的一个。 这里还需要考虑到一个小细节，dungeon是一个超级大的血包，这里一减dp[i][j]可能为负数，因为dp[i][j]必须是大于等于1的，所以我们最后还要处理一下。

1. 初始化 如图所示绿色三角形的位置会越界，为了防止越界，我们在创建dp表时多开一行多开一列，因为要求的时右一步和下一步两者的最小值，所以我们初始化dp表是初始化为最大（INT_MAX）,因为dp[i][j]表示以[i][j]位置为起点到达终点时需要的最低初始健康点数，最终救出公主时的健康点数应该为1，所以我们将最后两个位置的值初始化为1即可。
2. 填表顺序 从上往下填每一行，每一行从右往左
3. 返回值 因为我们从[0][0]位置为起点，所以我们最后返回dp[0][0]即可。

代码实现：

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        ///1.创建dp表
        int m = dungeon.size(),n = dungeon[0].size();
        vector<vector<int>> dp(m + 1,vector<int> (n + 1,INT_MAX));
        //2.初始化
        dp[m][n-1] = dp[m-1][n] = 1;
        //3.填表
        for(int i = m-1;i >= 0 ;i--)
        {
            for(int j = n-1;j >= 0 ;j--)
            {
                dp[i][j] = min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j];
                dp[i][j] = max(1,dp[i][j]);
            }
        }
        return dp[0][0];
    }
};

时间复杂度：O(m*n) 空间复杂度：O(m*n)