【动态规划篇】- 路径问题
62. 不同路径
题目链接： 62. 不同路径
题目解析：
-
状态表示
dp[i][j]表示：以[i][j]为终点时，一共有多少种路径。 -
状态转移方程
以[i][j]最近的几步来分析问题，要么从[i-1][j]位置向下走一步到达[i][j],要么从[i][j-1]向右走一步到达[i][j]。
所以dp[i][j]=dp[i - 1][j]+dp[i][j - 1] -
初始化
为了防止越界，我们就需要初始化下图中红色线画的这部分
这里我们有个小技巧，那就是让dp表多开一行和一列
因为到达[1][1]这个位置共有一种路径，所以我们仅需将dp[1][0]或者dp[0][1]位置初始化为1，其余位置初始化为0即可。 -
填表顺序
从上向下，从左向右 -
返回值
因为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
题目解析：
这道题和上面那道题极度的相似，只不过是加了个障碍物
-
状态表示
dp[i][j]表示：以[i][j]为终点时，一共有多少种路径。 -
状态转移方程
以距离[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]。 -
初始化
因为到达[1][1]这个位置共有一种路径，所以我们仅需将dp[1][0]或者dp[0][1]位置初始化为1，其余位置初始化为0即可。 -
填表顺序
从上向下，从左向右 -
返回值
因为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. 珠宝的最高价值
题目解析：
- 状态表示
dp[i][j]表示：以[i][j]为终点时，获得的珠宝的最高价值 - 状态转移方程
以最近的一步来划分问题，要么从[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]，因为数组整体向右下角移动了一位。 - 初始化
这道题我们申请dp表时也多开出一行和一列，为了不影响其余位置的值，我们将这一行和这一列初始化成0即可。 - 填表顺序
从上往下，自左向右 - 返回值
因为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. 下降路径最小和
题目解析：
- 状态表示
dp[i][j]表示：到达[i][j]位置时的最小下降路径 - 状态转移方程
以最近的一步来划分问题
要到达[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] - 初始化
为了保证填表的时候不越界，所以我们在创建dp表的时候多开一行，多开两列。
为了保证虚拟节点里面的值不影响填表，所以我们在初始化的时候将dp表里面的值都初始化为+∞，将第一行初始化为0即可。
- 填表顺序
从上往下 - 返回值
由于最后要求的是下降路径的和最小，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. 最小路径和
题目解析：
- 状态表示
dp[i][j]表示：到达[i][j]位置时的数字最小和 - 状态转移方程
以最近的一步来分析问题，到达[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] - 初始化
下图蓝色圆圈标出的地方会用到绿色方框处的值，此时会产生越界，为了防止越界，所以我们创建dp表的时候多开一行和一列
因为我们要求的是上边和左边小的那一个，所以我们在初始化dp表的时候初始化为+∞,将dp[0][1]或者dp[1][0]初始化为0即可 - 填表顺序
从上往下，从左往右 - 返回值
因为要求的是到达终点时路径上的数字的和最小，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. 地下城游戏
题目解析：
-
状态表示
我们的状态表示方法有两种
①以某个位置为结尾
②以某个位置为起点
这道题当我们尝试以某个位置为结尾考虑问题的时候，我们会发现我们还需要知道这个位置的下一个值，那么以某个位置为结尾来表示这道题是不行的。
所以我们就以[i][j]位置为起点定义状态表示
dp[i][j]表示：以[i][j]位置为起点到达终点时，所需要的最低初始健康点数 -
状态转移方程
我们以[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的，所以我们最后还要处理一下。
-
初始化
如图所示绿色三角形的位置会越界，为了防止越界，我们在创建dp表时多开一行多开一列，因为要求的时右一步和下一步两者的最小值，所以我们初始化dp表是初始化为最大（INT_MAX）,因为dp[i][j]表示以[i][j]位置为起点到达终点时需要的最低初始健康点数，最终救出公主时的健康点数应该为1，所以我们将最后两个位置的值初始化为1即可。 -
填表顺序
从上往下填每一行，每一行从右往左 -
返回值
因为我们从[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)
👍 如果对你有帮助，欢迎：
- 点赞 ⭐️
- 收藏 📌
- 关注 🔔