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

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即可。

4. 填表顺序
   从上向下，从左向右

5. 返回值
   因为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]
3. 初始化
   为了保证填表的时候不越界，所以我们在创建dp表的时候多开一行，多开两列。
   为了保证虚拟节点里面的值不影响填表，所以我们在初始化的时候将dp表里面的值都初始化为+∞，将第一行初始化为0即可。
   
4. 填表顺序
   从上往下
5. 返回值
   由于最后要求的是下降路径的和最小，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即可
4. 填表顺序
   从上往下，从左往右
5. 返回值
   因为要求的是到达终点时路径上的数字的和最小，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的，所以我们最后还要处理一下。
   

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

4. 填表顺序
   从上往下填每一行，每一行从右往左

5. 返回值
   因为我们从[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)

---

👍 如果对你有帮助，欢迎：

• 点赞 ⭐️
• 收藏 📌
• 关注 🔔