动态规划——地下城游戏

题目链接

leetcode在线oj题——地下城游戏

题目描述

恶魔们抓住了公主并将她关在了地下城 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.length
n == dungeon[i].length
1 <= m, n <= 200
-1000 <= dungeon[i][j] <= 1000

解题思路

之前介绍的动态规划题目都是从左上角开始，迭代动态规划方程，一直走到右下角，得到最终的结果，但是这道题是需要我们给出初始的血量，因此需要从右下角开始，向左上角迭代

当进入到负数的房间时，骑士会扣血，但是我们是从最后一个房间推导前面的房间，因此往前走遇到负数需要加血，遇到正数可以减血

而当前状态最小血量应该是走下面和走右面都可以支撑，因此是求下面和右面状态的较小者 - 当前房间的buff

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

如果得到的数字是负数，说明到这个位置骑士已经死了，这是不应该的，骑士最小也要有一点血，因此将其重新变为1点血

dp[i][j] = Math.max(1, dp[i][j]);

从右下角开始迭代需要考虑越界问题，最下面一行和最右面一列会出现越界，为了简化代码，可以将dp数组多添加一行一列，而为了不改变动态方程的有效性，最下面一行和最右面一列需要填入不影响其他位置的值——正无穷大

而为了使得最后一个房间的buff减益后还能剩一点血量，dp[m - 1][n] = dp[m][n - 1] = 1;

完整代码

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;;
        int n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1];

        for(int i = 0; i <= n; i++){
            dp[m][i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i <= m; i++) {
            dp[i][n] = Integer.MAX_VALUE;
        }
        dp[m - 1][n] = 1;
        dp[m][n - 1] = 1;

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = Math.max(1, dp[i][j]);
            }
        }
        return dp[0][0];
    }
}