LEETCODE 174. Dungeon Game 解题思路分析

题目大意：

地下城游戏

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。

-2 (K)	-3	3
-5	-10	1
10	30	-5 (P)

说明:

• 骑士的健康点数没有上限。
• 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=174

解题思路分析：

这道题描述了一大堆文字，其实简单来说，就是从二位数组的左上角出发，每次只能向右或者向下移动一步，每移动一次，生命值就加上当前格子中的数字，该数字可能为正或负，也可能为0，当走到右下角时，保证生命值至少要大于等于1。在这个条件下，起始生命值最少可为多少。但要注意一点，这道题不仅要保证在最后一步是生命值要大于0，而且在中间任何一步都要满足此条件才可以。

起初我用的是dfs深度遍历，然而却超时了，没有通过。后来才意识到要用到动态规划DP来解题。我们知道使用DP关键两点，第一要知道起始条件，第二要总结出一个公式。具体解法如下：

1. 我们定义一个二位数组dp[i][j]，i和j分别代表当前位置的横纵坐标，数组的值代表了当前位置下需要的最小生命值是多少。
2. 我们使用DP时要知道初始状态，然而这道题恰恰是要求初始状态。不过没关系，我们可以反过来思考，以右下角作为起点，因为求最小生命值，所以右下的起始值应为1。
3. 接下来考虑dp的公式，对于任意一点dp[i][j]，当前需要的最小生命值应该是下一步需要的最小生命值减去当前位置需要消耗掉的生命值。举个例子，比如，走到下一步时需要至少保证拥有5点生命值（例如下一步需要消耗 -4）。那么当前位置的最小生命值应该是5减去当前位置的生命值消耗，比如当前位置需要消耗-3点，所以，当前位置应该至少保证有8点生命，这样，拥有8点生命值进入当前位置，减去3，还剩5，再走到下一步减去4，剩下1点，可以保证活命。
4. 上面提到的公式还有一种例外需要考虑，还是使用上面的例子，如果当前点为dp[i][j]，已知走到下一步是要保证至少5点生命值，此时当前点的为增加生命值10（正数），这时套用上面的公式，5 – 10 = -5，也就是说进入当前位置时满足至少拥有-5点生命值即可，但小于1的值是不可行的，这时需要强行将生命值变为1。（如果按照 -5来计算，虽然能够保证走到最后一步时生命值是1，但是无法保证中间过程所有的值都大于0的条件，所以这是无效解。将负数强行变成1之后，走到最后一步时，虽然生命值会大于1，但这个数是满足条件的最优解。）
5. 最后总结一下公式，dp[i][j] = 下一步需要的最小生命值 – 当前位置消耗(补给)，如果 dp[i][j] < 1, dp[i][j] = 1。那么下一步是什么位置呢？因为题目说明了只能向右或向下走，因此下一步是 dp[i + 1][j] 或者 dp[i][j + 1]。最优解要选择其中的最小值，因此最终的公式应该为：

dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);

另外，上面的公式还需要考虑数组越界的问题，在写代码时需要注意。最后看下完整的实现代码。

public int calculateMinimumHP(int[][] dungeon) {
    // 用于保存进入每一步时需要的最小生命值
    int[][] dp = new int[dungeon.length][dungeon[0].length];
    int i = dungeon.length - 1;
    int j = dungeon[0].length - 1;
    // 初始化最后一步（右下角）时需要的最小生命值。
    dp[i][j] = dungeon[i][j] > 0 ? 1 : Math.abs(dungeon[i][j]) + 1;
    // 从右下角向左上角循环
    for (i = dungeon.length - 1; i >= 0; i--) {
        for (j = dungeon[0].length - 1; j >= 0; j--) {
            // 最后一步已经初始化过了，跳过
            if (i == dungeon.length - 1 && j == dungeon[0].length - 1) {
                continue;
            }
            // 得到当前进入当前位置时需要的最小生命值
            dp[i][j] = Math.max(1, Math.min(i + 1 >= dungeon.length ? Integer.MAX_VALUE : dp[i + 1][j],
                    j + 1 >= dungeon[0].length ? Integer.MAX_VALUE : dp[i][j + 1]) - dungeon[i][j]);
        }
    }
    return dp[0][0];
}

本题解法用时2ms。

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-174-dungeon-game-解题思路分析/