标题形貌：
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来救济公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立刻死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表现骑士将丧失健康点数）；其他房间要么是空的（房间里的值为 0），要么包罗增长骑士健康点数的邪术球（若房间里的值为正整数，则表现骑士将增长健康点数）。
为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士可以或许救济到公主所需的最低初始健康点数。
注意：任何房间都大概对骑士的健康点数造成威胁，也大概增长骑士的健康点数，包括骑士进入的左上角房间以及公主被羁系的右下角房间。
示例 1：
- <strong>输入：</strong>dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
- <strong>输出：</strong>7
- <strong>解释：</strong>如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下 ，则骑士的初始健康点数至少为 7 。
- <strong>输入：</strong>dungeon = [[0]]
- <strong>输出：</strong>1
提示：
- m == dungeon.length
- n == dungeon.length
- 1 <= m, n <= 200
- -1000 <= dungeon[j] <= 1000
标题解析：
这道题是比较难的。这道题我们可以形象的理解为打怪游戏，骑士的血条是>0的，在迷宫打怪的过程中，骑士会消耗自己的血条。但是，在某个位置会有血包，会让骑士的血条增长。这道题给了一个二维数组，骑士从左上角到右下角，骑士的血条一定是大于便是某个值的，不然的话那还救什么公主。
通过对示例1的分析，发现骑士的血条值最低应为7。
算法原理：动态规划
状态表现：
（经验+标题要求）同砚们大概会发现，这道题和上一道题一样（路径降落最小和），我们以某一个位置为末端这一条经验是推不出状态转移方程的，感兴趣的同砚可以去推导一下。这时，我们就不得不考虑其他的经验值了。既然以某一个位置为末端推导不出，那我们不妨试一下，如果是以某一个位置为起点呢？
dp[j]表现：从[i,j]位置出发到达终点，所需要的最低健康点数（血条值）。
状态转移方程：（分情况讨论）
不论是往那里走，都满意x+dp[j]>=dp[j+1]大概x+dp[j]>=dp[i+1][j],可以得到x>=dp[j+1]-dp[j]大概x>=dp[i+1][j]-dp[j]。
往右走：dp[j+1]-dp[j]
往下走：dp[i+1][j]-dp[j]
最低健康点数（血条值）：min(sp[j+1],dp[i+1][j])-dp[j];
处理下负数情况：dp[j]=max(1,dp[j]);
初始化：
(考虑边界情况）由于之前我们都需要考虑下标的映射关系，以是就显得很贫苦，为了方便，这道题的初始化我们仅只初始化最下边一行和最右边一行（不会初始化的考虑无穷大和特殊值）。
填表次序：
从下往上，从右往左。
返回值：
返回dp[0][0]
代码：
- class Solution {
- public:
- int calculateMinimumHP(vector<vector<int>>& d) {
- int m=d.size(),n=d[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+1][j],dp[i][j+1])-d[i][j];
- dp[i][j]=max(1,dp[i][j]);
- }
- }
- return dp[0][0];
-
- }
- };
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
