逆向动态规划-地下城救公主
程序员文章站
2022-06-27 14:46:07
题目来自力扣.174,一道很经典的动态规划题目一些恶魔抓住了公主(P)并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士(K)最初被安置在左上角的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球...
题目来自力扣.174,一道很经典的动态规划题目
一些恶魔抓住了公主(P)并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士(K)最初被安置在左上角的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。
有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。
为了尽快到达公主,骑士决定每次只向右或向下移动一步。
说明:
骑士的健康点数没有上限。
任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。
题解:
这道题目很容易想到动态规划的办法,自左上到左下,类似于避开障碍物寻找最短路径的题目。但是这种做法计算的是总路径的最小值,而题目要求的是最少用多少体力可以到达。最少用多少体力取决与两个中间量,
1.总路径之和(每次算体力都要用到)
2.在这条路径上的动态最小体力
自左上到左下的动态规划只能考虑其中的一种因素(1) ,而逆向动态规划(自右下到左上),可以直接考虑(2),从而忽视了影响因素(1),不需要去计算总路程之和,所以这道题应用逆向动态规划的思想,即可解决。
代码:
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int n = dungeon.size();
int m = dungeon[0].size();
vector<vector<int>>dp(n, vector<int>(m, 0));
if(dungeon[n-1][m-1]>0) dp[n-1][m-1]=1;
else dp[n-1][m-1]=-dungeon[n-1][m-1]+1;
for (int i = n-1; i >=0; i--) {
//最后一竖排赋值
if (i == n-1) { continue; }
if(dp[i+1][m-1]-dungeon[i][m-1]<1)
//如果这个格子所需的体力小于1(不需要体力即可走到终点) 那么设定这个格子的最小体力为1
//否则需要多少体力就填写多少体力dp
dp[i][m-1] =1;
else dp[i][m-1]=dp[i+1][m-1]-dungeon[i][m-1];
}
for (int i = m-1; i >= 0; i--) {
//最后一横排赋值
if (i == m-1) continue;
if(dp[n-1][i+1]-dungeon[n-1][i]<1)
dp[n-1][i]=1;
else dp[n-1][i]=dp[n-1][i+1]-dungeon[n-1][i];
}
for(int i=n-1-1;i>=0;i--){
for(int j=m-1-1;j>=0;j--){
dp[i][j]=max(min(dp[i+1][j],dp[i][j+1])-dungeon[i][j],1);
}
}
// for (int i = 0; i < n; i++) {
// //打印输出dp
// for (int j = 0; j < m; j++) {
// cout << dp[i][j];
// }
// cout << endl;
// }
return dp[0][0];
}
};
本文地址:https://blog.csdn.net/weixin_44866921/article/details/107330123
上一篇: 就发现钱没了