网站建设提升界面流畅程度,wordpress文章封面,浙江网站推广,专门做代理的网站文章目录1. 题目2. 解题1. 题目
一些坏人抓住了公主#xff08;P#xff09;并将她关在了地下城的右下角。 地下城是由 M x N 个房间组成的二维网格。 我们英勇的骑士#xff08;K#xff09;最初被安置在左上角的房间里#xff0c; 他必须穿过地下城并通过对抗坏人来拯救…
文章目录1. 题目2. 解题1. 题目
一些坏人抓住了公主P并将她关在了地下城的右下角。 地下城是由 M x N 个房间组成的二维网格。 我们英勇的骑士K最初被安置在左上角的房间里 他必须穿过地下城并通过对抗坏人来拯救公主。
骑士的初始健康点数为一个正整数。 如果他的健康点数在某一时刻降至 0 或以下他会立即死亡。
有些房间由坏人守卫因此骑士在进入这些房间时会失去健康点数若房间里的值为负整数则表示骑士将损失健康点数 其他房间要么是空的房间里的值为 0要么包含增加骑士健康点数的魔法球若房间里的值为正整数则表示骑士将增加健康点数。
为了尽快到达公主骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
例如考虑到如下布局的地下城如果骑士遵循最佳路径
右 - 右 - 下 - 下则骑士的初始健康点数至少为 7。-2 (K) -3 3
-5 -10 1
10 30 -5 (P)说明:
骑士的健康点数没有上限。任何房间都可能对骑士的健康点数造成威胁
也可能增加骑士的健康点数
包括骑士进入的左上角房间以及公主被监禁的右下角房间。来源力扣LeetCode 链接https://leetcode-cn.com/problems/dungeon-game 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
参考官方的解题正向不好计算最低的初始生命值反向考虑dp[i][j]表示走到 坐标处的所需的最低生命值
class Solution {
public:int calculateMinimumHP(vectorvectorint grid) {int m grid.size(), n grid[0].size(), i, j, minlife;vectorvectorint dp(m1,vectorint(n1, INT_MAX));dp[m][n-1] dp[m-1][n] 1;//处理边界更方便for(i m-1; i 0; --i){for(j n-1; j 0; --j){minlife min(dp[i1][j], dp[i][j1]);//使用较小的dp[i][j] max(minlife-grid[i][j], 1);//在 i,j,处你的生命值至少需要为1}}return dp[0][0];}
};12 ms 8.9 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
