174. Dungeon Game

wanglu1209 发布于2019-08-14 14:06 / 2115人阅读

摘要：题目解答这一题最重要的是把所剩血量初始化血量走这一步消耗的血量这句话读懂。那么我们假设是走完后所剩余的血量肯定是大于等于的。如果想存活下来，最少需要上一步血量，即上一步血量然后分类讨论上一步血量的可能性，注意边界情况的初始化即可。

题目：

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.

解答：
这一题最重要的是把：所剩血量＝初始化血量＋走这一步消耗的血量 >= 1 这句话读懂。那么我们假设f(i, j)是走完(i, j)后所剩余的血量（f(i, j)肯定是大于等于1的）。如果想存活下来，最少需要f(i, j) ＝ f(上一步血量）＋ dungeon(i, j) >= 1，即：f(i, j) = Math.max(1, f(上一步血量）- dungeon(i, j)). 然后分类讨论上一步血量的可能性，注意边界情况的初始化即可。

程序如下：

public class Solution {
    //State: f[i][j] is from (0, 0) to (i, j) the least health the knight should have
    //Function: f[i][j] + dungeon[i][j] >= 1 --> f[i][j] = Math.max(1 - dungeon[i][j], 1);
    //Intialize: f[i][n - 1] = Math.max(1 - f[i + 1][n - 1], 1), f[m - 1][i] = math.max(i - f[m - 1][i + 1], 1);
    //Result: f[0][0];
    public int calculateMinimumHP(int[][] dungeon) {
        if (dungeon == null || dungeon.length == 0 || dungeon[0].length == 0) {
            return 0;
        }
        
        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--) {
                int right = Math.max(1, f[i][j + 1] - dungeon[i][j]);
                int down = Math.max(1, f[i + 1][j] - dungeon[i][j]);
                f[i][j] = Math.min(right, down);
            }
        }
        
        return f[0][0];
    }
}

服务器托管专线服务 Dungeon game webrtc game game 域名备案

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64812.html

[leetcode]174. Dungeon Game

摘要：为了保证骑士可以最终到达，我们可以从终点逆向走到起点。为正数表示是药水，骑士可以相应降低初始血量。为负数表明要增加血量来保证存活。用二维空间来表示当前位置所需的最小血量，不断向左上方走直到起点。用来表示当前层与下一层。 The demons had captured the princess (P) and imprisoned her in the bottom-right cor...

siberiawolf 2019-08-14 16:52 评论0 收藏0
[Leetcode] Dungeon Game 地牢游戏

摘要：动态规划复杂度时间空间递归栈思路骑士向右或者向下走，如果血量小于就死掉了，这会使得计算变得很复杂。假设表示点和的血量，表示走到和要扣除的血量。最右下角那个节点没有待逆推的节点，所以我们假设其逆推节点的血量为。 Dungeon Game The demons had captured the princess (P) and imprisoned her in the bottom-r...

taoszu 2019-08-14 12:45 评论0 收藏0
Vultr机房测评 - Vultr美国亚特兰大Atlanta机房综合速度和线路去程回程测

摘要：美国亚特兰大机房速度怎么样商家也有提供亚特兰大机房。亚特兰大是美国佐治亚州首府和最大的工商业城市位于美国东部。这篇文章，我们一起看看亚特兰大机房吧。Vultr 美国亚特兰大机房速度怎么样？Vultr 商家也有提供亚特兰大Atlanta机房。Atlanta亚特兰大是美国佐治亚州首府和最大的工商业城市、位于美国东部。从PING速度看，速度上相对是不如洛杉矶或者西雅图等稍微偏西岸机房的，但是对于我...

fox_soyoung 2021-08-30 09:47 评论0 收藏0
Vultr机房测评 - Vultr英国伦敦London机房综合速度和线路去程回程测试

摘要：商家欧洲机房目前包含英国伦敦荷兰德国法国四个机房。第四英国伦敦机房配置和读写测试第五英国伦敦机房网络媒体支持测试第六英国伦敦机房路由回程测试总结，以上是欧洲机房伦敦机房的基本性能测试。Vultr 商家欧洲机房目前包含英国伦敦、荷兰、德国、法国四个机房。一般欧洲机房适合有需要欧洲IP节点业务需要的，包括我们有需要欧洲外贸业务需要用到欧洲本土的机房。比如老蒋遇到有不少远程操作欧洲亚马逊业务的会开...

lavor 2021-08-23 09:45 评论0 收藏0