【动态规划精选题目】2、路径问题模型
此动态规划系列主要讲解大约10个系列【后续持续更新】
本篇讲解路径问题模型中的6道经典题,会在讲解题目同时给出AC代码
目录
?
?1、不同路径
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m + 1, vector<int> (n + 1));
dp[0][1] = 1;//此位置的虚拟节点的初始化为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];
}
};
2、不同路径2
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& ob) {
int m = ob.size(), n = ob[0].size();
vector<vector<int>> dp(m + 1, vector<int> (n + 1));
dp[1][0] = 1;//虚拟节点设置为1
for (int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
if(ob[i - 1][j - 1] != 1)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
return dp[m][n];
}
};
3、珠宝的最大价值
?
class Solution {
public:
int jewelleryValue(vector<vector<int>>& frame) {
int m = frame.size(), n = frame[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));//会自动初始化为0
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
//因为设置虚拟节点,则frame[i-1][j-1],-1后拿到的才是原位置的价值
return dp[m][n];
}
};
4、下降路径最小和
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int n = matrix.size();//方阵
vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));
//INT_MAX表示一个 32 位符号整数所能够表示的最大值
//初始化第一行
for (int i = 0; i < n + 2; i++) dp[0][i] = 0;
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 minimum = INT_MAX;
for (int i = 1; i <= n; i++)
minimum = min(minimum, dp[n][i]);
return minimum;
}
};
5、最小路径和
?
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
dp[0][1] = dp[1][0] = 0;
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];
}
};
6、地下城游戏
分析题目,模拟示例1:
?
2、状态转移方程?
怎样能从 ( i, j ) 位置正确进入到 ( i, j + 1 ) 位置呢?因为dp表里存的是从某个位置出发到终点时的最低血量. 故假设 ( i, j ) 位置此时最低初始血量为 X, 想要走出这个位置就需要先击败里面的恶魔 dungeon[i][j], 之后剩余血量 X + dungeon[i][j]【但也不排除dungeon[i][j]位置是血包,但不影响结果】 也就走出(i, j)位置后的血量必须>=?( i, j+1 ) 的最低初始血量 dp[i][j+1] 才能进入, 否则无法到达终点.当 X + dungeon[i][j] >= dp[i][j+1] 时才有机会到达终点. 题目要求最低初始血量, 取等时即可。
此时所需dp[i][j+1] - dungeon[i][j]
同理,从 ( i, j ) 位置到?( i+1, j ) 位置后想要到达终点所需要的最低初始血量为
dp[i+1][j] - dungeon[i][j]
由于我们求的是从某点出发到终点的最低初始血量, 所以
状态转移方程:dp[i][j] = min(dp[i][j+1], dp[i+1][j] ) - dungeon[i][j]
注意:当 dungeon[i][j] 非常大时, dp[i][j] 最终会是一个< 0 的数。【但最低血量<=0都是会die的】
即( i, j ) 位置里面有个非常大的血包(dungeon[i][j]),此时从( i, j ) 位置走出去就是是负数了,可是按理说应该已经die了,不能走到下一位置了(dp[i][j+1],或dp[i+1][j])。那么这里就是没有考虑血包很大的问题,只是考虑了部分情况,按理说血包很大是可以走出去的,这是算是误判了,故必须保证在走出?( i, j ) 位置后它的血量>?0。
因此最终需对dp[i][j]进行处理,dp[i][j] = max( 1, dp[i][j]?
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int m = dungeon.size(), n = dungeon[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
dp[m][n - 1] = dp[m - 1][n] = 1;
for (int i = m - 1; i >= 0; i--)
for (int j = n - 1; j >= 0; j--)
{
dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];
dp[i][j] = max(1, dp[i][j]);
}
return dp[0][0];
}
};
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!