The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.
The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).
In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.
Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.
For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN
.
-2 (K) | -3 | 3 |
-5 | -10 | 1 |
10 | 30 | -5 (P) |
Notes:
- The knight's health has no upper bound.
- Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.
乍一看,这个问题和"Maximum/Minimum Path Sum"问题很相似。然而,具有全局最大HP(生命值)收益的路径并不一定可以保证最小的初始HP,因为题目中具有限制条件:HP不能≤0。例如,考虑下面的两条路径:0 -> -300 -> 310 -> 0 和 0 -> -1 -> 2 -> 0。这两条路径的净HP收益分别是-300 + 310 = 10 与 -1 + 2 = 1。第一条路径的净收益更高,但是它所需的初始HP至少是301,才能抵消第二个房间的-300HP损失,而第二条路径只需要初始HP为2就可以了。 幸运的是,这个问题可以通过“table-filling”(表格填充)动态规划算法解决,与其他"grid walking"(格子行走)问题类似: 首先,我们应该维护一个2维数组D,与地牢数组的大小相同,其中D[i][j]代表可以保证骑士在进入房间(i,j)之前,探索其余地牢时能够存活下来的最小HP。显然D[0][0]就是我们随后需要的最终答案。因此,对于这个问题,我们需要从右下角到左上角填充表格。 然后,我们来计算离开房间(i,j)时的最小HP。从这一点出发只有两条路径可选:(i + 1, j)和(i, j + 1)。当然我们会选择拥有更小D值的那个房间,换言之,骑士完成剩下的旅途所需的较小HP。因此我们有: min_HP_on_exit = min(D[i+1][j], D[i][j+1]) 现在D[i][j]可以通过dungeon[i][j]和min_HP_on_exit,根据下面的情景得出: 如果dungeon[i][j] == 0,那么在这个房间里很安全。 骑士离开这个房间时的HP和他进入房间时的HP保持一致, 也就是说 D[i][j] = min_HP_on_exit. 如果dungeon[i][j] < 0,那么骑士在进入该房间之前的HP > 离开房间时的HP,min_HP_on_exit才能抵消他在该房间中的HP损失。 最小HP花费就是 "-dungeon[i][j]", 因此我们有公式 D[i][j] = min_HP_on_exit - dungeon[i][j]. 如果dungeon[i][j] > 0, 那么骑士在进入房间(i, j) 时的HP只需为min_HP_on_exit - dungeon[i][j],因为他可以在该房间内获得数值为"dungeon[i][j]"的HP收益。 不过,这种情况下min_HP_on_exit - dungeon[i][j]的数值可能≤0。 此时,我们需要把值置为1以确保D[i][j]为正整数: D[i][j] = max(min_HP_on_exit - dungeon[i][j], 1)。 注意 dungeon[i][j] > 0 条件下的等式实际上可以覆盖其他两种情况。 因此我们可以把三种情况归纳为同一个等式: 亦即: D[i][j] = max(min_HP_on_exit - dungeon[i][j], 1) dungeon[i][j]可以为任意值。 D[0][0]就是最终答案。 此外,像许多其他"table-filling"问题一样,二维数组D可以用一维滚动数组替代。
状态转移方程:
代码:
public int calculateMinimumHP(int[][] dungeon) { int m = dungeon.length, n = dungeon[0].length; int[][] f = new int[m][n]; f[m-1][n-1] = Math.max(1, 1-dungeon[m-1][n-1]); for(int i=m-2; i>=0; i--) { f[i][n-1] = Math.max(1, f[i+1][n-1]-dungeon[i][n-1]); } for(int j=n-2; j>=0; j--) { f[m-1][j] = Math.max(1, f[m-1][j+1]-dungeon[m-1][j]); } for(int i=m-2; i>=0; i--) { for(int j=n-2; j>=0; j--) { f[i][j] = Math.max(1, Math.min(f[i+1][j], f[i][j+1])-dungeon[i][j]); } } return f[0][0]; }
相关推荐
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
IDEA 插件,lettcode刷题,leetcode-editor7.4版本下载进行本地导入(直接将压缩包拖进IDEA即可)
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
在IDE中解决LeetCode问题,支持leetcode.com与leetcode-cn.com,满足基本的做题需求。 理论上支持: IntelliJ IDEA PhpStorm WebStorm PyCharm RubyMine AppCode CLion GoLand DataGrip Rider MPS Android Studio。
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
leetcode 答案解析 golang解答
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
leetcode-helper-1.7.1
970. 强整数对数运算function powerfulIntegers(x: number, y: number, bound: number): numb
然后进入到LeetCode-Spider目录中修改config.json,其中outputDir需要填写该工程的/docs/views文件夹路径 { "username": "aaa", "password": "bbb", "outputDir": "/Users/liuyao/Downloads/LeetCode-Blog-Test/docs...
leetcode-tag-dynamic programming
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode-tag-Tree
leetcode-tag-Stack
leetcode-tag-array