免费视频网站素材,企业应用平台下载,朱腾鹏个人网站,4414站长平台题目
174. 地下城游戏
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里#xff0c;他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健…题目
174. 地下城游戏
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下他会立即死亡。
有些房间由恶魔守卫因此骑士在进入这些房间时会失去健康点数若房间里的值为负整数则表示骑士将损失健康点数其他房间要么是空的房间里的值为 0要么包含增加骑士健康点数的魔法球若房间里的值为正整数则表示骑士将增加健康点数。
为了尽快解救公主骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意任何房间都可能对骑士的健康点数造成威胁也可能增加骑士的健康点数包括骑士进入的左上角房间以及公主被监禁的右下角房间。 示例 1 输入dungeon [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出7
解释如果骑士遵循最佳路径右 - 右 - 下 - 下 则骑士的初始健康点数至少为 7 。
示例 2
输入dungeon [[0]]
输出1提示
m dungeon.lengthn dungeon[i].length1 m, n 200-1000 dungeon[i][j] 1000 代码
int min(int a,int b)
{return (ab)?a:b;
}
int max(int a,int b)
{return (ab)?a:b;
}
int calculateMinimumHP(int** dungeon, int dungeonSize, int* dungeonColSize)
{int dp[202][202]{0};int ndungeonColSize[0];int mdungeonSize;for(int i0;i202;i){for(int j0;j202;j){dp[i][j]INT_MAX;}}dp[m-1][n] dp[m][n-1]1;//[i,j]以i,j位置为起点到达终点所需的最小点数//那么为什么不能用i,j位置为结尾从起点到达所需的最小点数因为这个位置不仅受前面影响也是受后面的影响的for(int im-1;i0;i--){for(int jn-1;j0;j--){//分两种情况//从i,j位置往右走假设dp i,j位置里面是xx既要能走过原来的也要能走要下一个因此xdp[i][j1]-dungeon[i][j]//从i,j位置往下走同理xdp[i1][j]-dungeon[i][j]dp[i][j]min(dp[i1][j],dp[i][j1])-dungeon[i][j];//如果这个血包很大也就是dungeon[i-1][j-1]很大dp[i][j]会变成负的//dungeon[i-1][j-1],很大就是说就算过来的是负值也可以走到结尾但是过来不能是负的最小也要是1dp[i][j]max(1,dp[i][j]);}}return dp[0][0];
}
