leetcode刷题笔记174.地下城游戏

题目
一些恶魔抓住了公主&＃xff08;P&＃xff09;并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士&＃xff08;K&＃xff09;最初被安置在左上角的房间里&＃xff0c;他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下&＃xff0c;他会立即死亡。

有些房间由恶魔守卫&＃xff0c;因此骑士在进入这些房间时会失去健康点数&＃xff08;若房间里的值为负整数&＃xff0c;则表示骑士将损失健康点数&＃xff09;&＃xff1b;其他房间要么是空的&＃xff08;房间里的值为 0&＃xff09;&＃xff0c;要么包含增加骑士健康点数的魔法球&＃xff08;若房间里的值为正整数&＃xff0c;则表示骑士将增加健康点数&＃xff09;。

为了尽快到达公主&＃xff0c;骑士决定每次只向右或向下移动一步。

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

示例
输入&＃xff1a;

-2 -3 3-5 -10 110 30 -5


输出&＃xff1a;7
解释:考虑到如下布局的地下城&＃xff0c;如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下&＃xff0c;则骑士的初始健康点数至少为 7。

解法

1. 一开始觉得比较简单&＃xff0c;就是动态规划&＃xff0c;主要维护两个点&＃xff1a;
   1. 从出发点到当前点的路径和 &＃xff08;越大越好&＃xff09;
   2. 从出发点到当前点所需的最小初始值 &＃xff08;越小越好&＃xff09;
2. 但是细想发现不对&＃xff0c;如果按照从左到右的顺序进行动态规划&＃xff0c;这两个重要程度相同的参数都会影响后续的决策
3. 举例&＃xff1a;

原始数组:1 -3 30 -2 0-3 -3 -31. 假设走到(1,2)这个坐标2. 路线一 &＃xff08;0,0&＃xff09;-> (0,1) -> (0,2) -> (1,2)从出发到当前点的路径和为 1-3&＃43;3&＃43;0 &＃61; 1从出发点到当前点所需的最小初始值 33. 路线二 (0,0) -> (1,0) -> (1,1) -> (1,2)从出发到当前点的路径和为 1&＃43;0-2&＃43;0&＃61;-1从出发点到当前点所需的最小初始值 24. 不同的路线&＃xff0c;路径和、最小初始值都很重要&＃xff0c;都会影响后续的决策&＃xff0c;无法确定到达&＃xff08;1,2)的最佳方案路线一虽然到达点(1,2)时&＃xff0c;累积血量为1&＃xff0c;但是初始值最少为3路线二虽然初始值需要2&＃xff0c;但是累积的血量为-1没法判断哪条路好


4. 所以我们选择们考虑从右下往左上进行动态规划。令 dp[i][j]表示从坐标 (i,j)到终点所需的最小初始值&＃xff0c;也就说走进这个坐标至少要有这么多血&＃xff0c;才能成功走到终点。
5. 对于dp[i][j]&＃xff0c;可以由dp[i&＃43;1][j]或者dp[i][j&＃43;1]得到&＃xff0c;dp的值会选择(走进这个坐标至少要拥有血量)少的那个&＃xff0c;如下图dp[0][0]&＃xff0c;一定会选择往下走&＃xff0c;因为dp[1][0]
6. 需要再结合原始数组的[i][j]&＃xff0c;与1比较&＃xff0c;如下图dp[1][0]&＃xff0c;我即使以负的血量&＃xff08;4-5&＃xff09;走进这个坐标&＃xff0c;也能走到终点&＃xff0c;但是要移动的话&＃xff0c;血量至少为1
7. 可以得出dp[i][j]&＃61;max(min(dp[i&＃43;1][j],dp[i][j&＃43;1])−dungeon(i,j),1)
8. 需要注意边界&＃xff0c;当dp[i][j]是右下角时需要dp[i&＃43;1][j]和dp[i][j&＃43;1]的值&＃xff0c;这两个值两个都为1&＃xff0c;因为到达终点至少需要1点的血量
9. 举例

原始数组&＃xff1a;1 -35 -3dp数组:1 7&＃61;4-(-3) INT_MAX1&＃61;max(min(4,INT_MAX)-5,1) 4&＃61;1-(-3) 1INT_MAX 1


10. 所以返回结果为dp[0][0]

测试数据

原始数组&＃xff1a;0 0 01 1 -1结果&＃xff1a;1原始数组&＃xff1a;-3 5结果&＃xff1a;4原始数组&＃xff1a;1 -3 30 -2 0-3 -3 -3结果&＃xff1a;3


代码

#include
#include
#include
using namespace std;
class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int m &＃61; dungeon.size(), n &＃61; dungeon[0].size();vector<vector<int>> dp(m &＃43; 1, vector<int>(n &＃43; 1, INT_MAX));dp[m][n - 1] &＃61; dp[m - 1][n] &＃61; 1;for (int i &＃61; m - 1; i >&＃61; 0; i--) {for (int j &＃61; n - 1; j >&＃61; 0; j--) {dp[i][j] &＃61; max(min(dp[i &＃43; 1][j], dp[i][j &＃43; 1]) - dungeon[i][j], 1);}}return dp[0][0];}
};int main()
{Solution s ;vector<vector<int>> m(3,vector<int>(3));m[0][0]&＃61;-2;m[0][1]&＃61;-3;m[0][2]&＃61;3;m[1][0]&＃61;-5;m[1][1]&＃61;-10;m[1][2]&＃61;1;m[2][0]&＃61;10;m[2][1]&＃61;30;m[2][2]&＃61;-5;cout<<s.calculateMinimumHP(m);//7return 0;
}


今天也是爱zz的一天哦&＃xff01;