LeetCode_动态规划_困难_174.地下城游戏
2023-09-27 14:25:46 时间
1.题目
一些恶魔抓住了公主(P)并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士(K) 最初被安置在左上角的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。
有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。
为了尽快到达公主,骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
例如,考虑到如下布局的地下城,如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下,则骑士的初始健康点数至少为 7。
说明:
骑士的健康点数没有上限。
任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/dungeon-game
2.思路
(1)动态规划
思路见本题官方题解。
3.代码实现(Java)
//思路1————动态规划
public int calculateMinimumHP(int[][] dungeon) {
if (dungeon == null) {
return 0;
}
int N = dungeon.length;
int M = dungeon[0].length;
/*
dp[i][j]:表示从坐标(i,j)到终点所需的最小初始值
即当到达坐标(i,j)时,如果此时我们的路径和大于等于dp[i][j],我们就能到达终点
*/
int[][] dp = new int[N + 1][M + 1];
for (int i = 0; i <= N; i++) {
/*
当i=n−1或者j=m-1时,状态转移方程需要用到的dp[i][j+1]和dp[i+1][j]中有无效值,
因此代码实现中给无效值赋值为极大值
*/
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
dp[N][M - 1] = 1;
dp[N - 1][M] = 1;
for (int i = N - 1; i >= 0; i--) {
for (int j = M - 1; j >= 0; j--) {
int minValue = Math.min(dp[i + 1][j], dp[i][j + 1]);
dp[i][j] = Math.max(minValue - dungeon[i][j], 1);
}
}
//dp[0][0]表示从坐标(0,0)到终点所需的最小初始值
return dp[0][0];
}
相关文章
- Leetcode: Word Ladder
- 【Leetcode】23. 合并K个升序链表(困难)
- [LeetCode] Maximum Subarray
- Leetcode每日一题(9.12)最长递增序列的个数
- 131、【贪心算法】leetcode ——55. 跳跃游戏(贪心策略)(C++版本)
- 【LeetCode】229. Majority Element II
- [LeetCode] 1340. Jump Game V 跳跃游戏之五
- [LeetCode] 1306. Jump Game III 跳跃游戏之三
- [LeetCode] 877. Stone Game 石子游戏
- [LeetCode] Card Flipping Game 翻卡片游戏
- [LeetCode] Similar RGB Color 相似的红绿蓝颜色
- [LeetCode] Chalkboard XOR Game 黑板亦或游戏
- [LeetCode] 24 Game 二十四点游戏
- [LeetCode] Minesweeper 扫雷游戏
- [LeetCode] Design Snake Game 设计贪吃蛇游戏
- [LeetCode] 294. Flip Game II 翻转游戏之二
- [LeetCode] 293. Flip Game 翻转游戏
- [LeetCode] 321. Create Maximum Number 创建最大数
- [LeetCode] Nim Game 尼姆游戏
- [LeetCode] 30. Substring with Concatenation of All Words 串联所有单词的子串
- [LeetCode] 40. Combination Sum II 组合之和之二
- [LeetCode] 45. Jump Game II 跳跃游戏之二
- [LeetCode] 55. Jump Game 跳跃游戏
- leetcode 79. Word Search 单词搜索
- leetcode算法112. 路径总和