• 【leetcode热题】 地下城游戏

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

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

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

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

    返回确保骑士能够拯救到公主所需的最低初始健康点数。

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

    示例 1：

    输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出：7
解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下 ，则骑士的初始健康点数至少为 7 。

    示例 2：

    输入：dungeon = [[0]]
输出：1

    解法一 回溯法

    最直接暴力的方法就是做搜索了，在每个位置无非就是向右向下两种可能，然后去尝试所有的解，然后找到最小的即可，也就是做一个 DFS 或者说是回溯法。

    1. //全局变量去保存最小值
    2. int minHealth = Integer.MAX_VALUE;
    3.  
    4. public int calculateMinimumHP(int[][] dungeon) {
    5.     //calculateMinimumHPHelper 四个参数
    6.     //int x, int y, int health, int addHealth, int[][] dungeon
    7.     //x, y 代表要准备到的位置，x 代表是哪一列，y 代表是哪一行
    8.     //health 代表当前的生命值
    9.     //addHealth 代表当前已经增加的生命值
    10.     //初始的时候给加 1 点血，addHealth 和 health 都是 1
    11.     calculateMinimumHPHelper(0, 0, 1, 1, dungeon);
    12.     return minHealth;
    13. }
    14.  
    15. private void calculateMinimumHPHelper(int x, int y, int health, int addHealth, int[][] dungeon) {
    16.     //加上当前位置的奖励或惩罚
    17.     health = health + dungeon[y][x];
    18.     //此时是否需要加血，加血的话就将 health 加到 1
    19.     if (health <= 0) {
    20.         addHealth = addHealth + Math.abs(health) + 1;
    21.     }
    22.  
    23.     //是否到了终点
    24.     if (x == dungeon[0].length - 1 && y == dungeon.length - 1) {
    25.         minHealth = Math.min(addHealth, minHealth);
    26.         return;
    27.     }
    28.  
    29.     //是否加过血
    30.     if (health <= 0) {
    31.         //加过血的话，health 就变为 1
    32.         if (x < dungeon[0].length - 1) {
    33.             calculateMinimumHPHelper(x + 1, y, 1, addHealth, dungeon);
    34.         }
    35.         if (y < dungeon.length - 1) {
    36.             calculateMinimumHPHelper(x, y + 1, 1, addHealth, dungeon);
    37.         }
    38.     } else {
    39.         //没加过血的话，health 就是当前的 health
    40.         if (x < dungeon[0].length - 1) {
    41.             calculateMinimumHPHelper(x + 1, y, health, addHealth, dungeon);
    42.         }
    43.         if (y < dungeon.length - 1) {
    44.             calculateMinimumHPHelper(x, y + 1, health, addHealth, dungeon);
    45.         }
    46.     }
    47.  
    48. }

    然后结果是意料之中的，会超时。

    然后我们就需要剪枝，将一些情况提前结束掉，最容易想到的就是，如果当前加的血已经超过了全局最小值，那就可以直接结束，不用进后边的递归。

    1. if (addHealth > minHealth) {
    2.     return;
    3. }
    Copy

    然后发现对于给定的 test case 并没有什么影响。

    之所以超时，就是因为我们会经过很多重复的位置，比如

    1. 0 1 2
    2. 3 4 5
    3. 6 7 8
    4. 如果按 DFS，第一条路径就是 0 -> 1 -> 2 -> 5 -> 8
    5. 然后通过回溯，第二次判断的路径就会是 0 -> 1 -> 4 -> 5 -> ...
    6. 我们会发现它又会来到 5 这个位置
    7. 其他的也类似，如果表格很大的话，不停的回溯，一些位置会经过很多次

    接下来，就会想到用 map 去缓冲我们过程中求出的解，key 话当然是 x 和 y 了，value 呢？存当前的 health 和 addhealth？那第二次来到这个位置的时候，我们并不能做什么，比如举个例子。

    第一次来到 (3,5) 的时候，health 是 5，addhealth 是 6。

    第二次来到 (3,5) 的时候，health 是 4，addhealth 是 7，我们什么也做不了，我们并不知道未来它会走什么路。

    因为走的路是由 health 和 addhealth 共同决定的，此时来到相同的位置，由于 health 和 addhealth 都不一样，所以未来的路也很有可能变化，所以我们并不能通过缓冲结果来剪枝。

    我们最多能判断当 x、y、health 和 addhealth 全部相同的时候提前结束，但这种情况也很少，所以并不能有效的加快搜索速度。

    这条路看起来到死路了，我们换个思路，去用动态规划。

    动态规划的关键就是去定义我们的状态了，这里直接将要解决的问题定义为我们的状态。

    用 dp[i][j] 存储从起点 (0, 0) 到达 (i, j) 时候所需要的最小初始生命值。

    到达 (i,j) 有两个点，(i-1, j) 和 (i, j-1)。

    接下来就需要去推导状态转移方程了。

    1. * * 8 * 
    2. * 7 ! ?
    3. ? ? ? ?

    假如我们要求上图中 ! 位置的 dp，假设之前的 dp 已经都求出来了。

    那么 dp 是等于感叹号上边的 dp 还是等于它左边的 dp 呢？选较小的吗？

    但如果 8 对应的当时的 health 是 100，而 7 对应的是 5，此时更好的选择应该是 8。

    那就选 health 大的呗，那 dp 不管了吗？极端的例子，假如此时的位置已经是终点了，很明显我们应该选择从左边过来，也就是 7 的位置过来，之前的 health 并不重要了。

    所以推到这里会发现，因为我们有两个不确定的变量，一个是 dp ，也就是从起点 (0, 0) 到达 (i, j) 时候所需要的最小初始生命值，还有一个就是当时剩下的生命值。

    当更新 dp 的时候我们并不知道它应该是从上边下来，还是从左边过来有利于到达终点的时候所需的初始生命值最小。

    换句话讲，依赖过去的状态，并不能指导我们当前的选择，因为还需要未来的信息。

    所以到这里，我再次走到了死胡同，就去看 Discuss 了，这里分享下别人的做法。

    解法二 递归

    看到 这里 评论区的一个解法。

    所需要做的就是将上边动态规划的思路逆转一下。

    1.   ↓
    2. → *

    之前我们考虑的是当前这个位置，它应该是从上边下来还是左边过来会更好些，然后发现并不能确定。

    现在的话，看下边的图。

    1. * → x  
    2. ↓
    3. y

    我们现在考虑从当前位置，应该是向右走还是向下走，这样我们是可以确定的。

    如果我们知道右边的位置到终点的需要的最小生命值是 x，下边位置到终点需要的最小生命值是 y。

    很明显我们应该选择所需生命值较小的方向。

    如果 x < y，我们就向右走。

    如果 x > y，我们就向下走。

    知道方向以后，当前位置到终点的最小生命值 need 就等于 x 和 y 中较小的值减去当前位置上边的值。

    如果算出来 need 大于 0，那就说明我们需要 need 的生命值到达终点。

    如果算出来 need 小于等于 0，那就说明当前位置增加的生命值很大，所以当前位置我们只需要给一个最小值 1，就足以走到终点。

    举个具体的例子就明白了。

    如果右边的位置到终点的需要的最小生命值是 5，下边位置到终点需要的最小生命值是 8。

    所以我们选择向右走。

    如果当前位置的值是 2，然后 need = 5 - 2 = 3，所以当前位置的初始值应该是 3。

    如果当前位置的值是 -3，然后 need = 5 - (-3) = 8，所以当前位置的初始值应该是 8。

    如果当前位置的值是 10，说明增加的生命值很多，need = 5 - 10 = -5，此时我们只需要将当前位置的生命值初始为 1 即可。

    然后每个位置都这样考虑，递归也就出来了。

    递归出口也很好考虑， 那就是最后求终点到终点需要的最小生命值。

    如果终点位置的值是正的，那么所需要的最小生命值就是 1。

    如果终点位置的值是负的，那么所需要的最小生命值就是负值的绝对值加 1。

    1. public int calculateMinimumHP(int[][] dungeon) {
    2.     return calculateMinimumHPHelper(0, 0, dungeon);
    3. }
    4.  
    5. private int calculateMinimumHPHelper(int i, int j, int[][] dungeon) {
    6.     //是否到达终点
    7.     if (i == dungeon.length - 1 && j == dungeon[0].length - 1) {
    8.         if (dungeon[i][j] > 0) {
    9.             return 1;
    10.         } else {
    11.             return -dungeon[i][j] + 1;
    12.         }
    13.     }
    14.     //右边位置到达终点所需要的最小值，如果已经在右边界，不能往右走了，赋值为最大值
    15.     int right = j < dungeon[0].length - 1 ? calculateMinimumHPHelper(i, j + 1, dungeon) : Integer.MAX_VALUE;
    16.     //下边位置到达终点需要的最小值，如果已经在下边界，不能往下走了，赋值为最大值
    17.     int down = i < dungeon.length - 1 ? calculateMinimumHPHelper(i + 1, j, dungeon) : Integer.MAX_VALUE;
    18.     //当前位置到终点还需要的生命值
    19.     int need = right < down ? right - dungeon[i][j] : down - dungeon[i][j];
    20.     if (need <= 0) {
    21.         return 1;
    22.     } else {
    23.         return need;
    24.     }
    25. }

    当然还是意料之中的超时了。

    不过不要慌，还是之前的思想，我们利用 map 去缓冲中间过程的值，也就是 memoization 技术。

    这个 map 的 key 和 value 就显而易见了，key 是坐标 i,j，value 的话就存当最后求出来的当前位置到终点所需的最小生命值，也就是 return 前同时存进 map 中。

    1. public int calculateMinimumHP(int[][] dungeon) {
    2.     return calculateMinimumHPHelper(0, 0, dungeon, new HashMap<String, Integer>());
    3. }
    4.  
    5. private int calculateMinimumHPHelper(int i, int j, int[][] dungeon, HashMap<String, Integer> map) {
    6.     if (i == dungeon.length - 1 && j == dungeon[0].length - 1) {
    7.         if (dungeon[i][j] > 0) {
    8.             return 1;
    9.         } else {
    10.             return -dungeon[i][j] + 1;
    11.         }
    12.     }
    13.     String key = i + "@" + j;
    14.     if (map.containsKey(key)) {
    15.         return map.get(key);
    16.     }
    17.     int right = j < dungeon[0].length - 1 ? calculateMinimumHPHelper(i, j + 1, dungeon, map) : Integer.MAX_VALUE;
    18.     int down = i < dungeon.length - 1 ? calculateMinimumHPHelper(i + 1, j, dungeon, map) : Integer.MAX_VALUE;
    19.     int need = right < down ? right - dungeon[i][j] : down - dungeon[i][j];
    20.     if (need <= 0) {
    21.         map.put(key, 1);
    22.         return 1;
    23.     } else {
    24.         map.put(key, need);
    25.         return need;
    26.     }
    27. }

    解法三 动态规划

    其实解法二递归写完以后，很快就能想到动态规划怎么去解了。虽然它俩本质是一样的，但用动态规划可以节省递归压栈的时间，直接从底部往上走。

    我们的状态就定义成解法二递归中返回的值，用 dp[i][j] 表示从 (i, j) 到达终点所需要的最小生命值。

    状态转移方程的话和递归也一模一样，只需要把函数调用改成取直接取数组的值。

    因为对于边界的情况，我们需要赋值为最大值，所以数组的话我们也扩充一行一列将其初始化为最大值，比如

    1. 奖惩数组
    2. 1   -3   3
    3. 0   -2   0
    4. -3  -3   -3
    5.  
    6. dp 数组
    7. 终点位置就是递归出口时候返回的值，边界扩展一下
    8. 用 M 表示 Integer.MAXVALUE
    9. 0 0 0 M
    10. 0 0 0 M
    11. 0 0 4 M
    12. M M M M
    13.  
    14. 然后就可以一行一行或者一列一列的去更新 dp 数组，当然要倒着更新
    15. 因为更新 dp[i][j] 的时候我们需要 dp[i+1][j] 和 dp[i][j+1] 的值

    然后代码就出来了，可以和递归代码做个对比。

    1. public int calculateMinimumHP(int[][] dungeon) {
    2.     int row = dungeon.length;
    3.     int col = dungeon[0].length;
    4.     int[][] dp = new int[row + 1][col + 1];
    5.     //终点所需要的值
    6.     dp[row - 1][col - 1] = dungeon[row - 1][col - 1] > 0 ? 1 : -dungeon[row - 1][col - 1] + 1;
    7.     //扩充的边界更新为最大值
    8.     for (int i = 0; i <= col; i++) {
    9.         dp[row][i] = Integer.MAX_VALUE;
    10.     }
    11.     for (int i = 0; i <= row; i++) {
    12.         dp[i][col] = Integer.MAX_VALUE;
    13.     }
    14.  
    15.     //逆过来更新
    16.     for (int i = row - 1; i >= 0; i--) {
    17.         for (int j = col - 1; j >= 0; j--) {
    18.             if (i == row - 1 && j == col - 1) {
    19.                 continue;
    20.             }
    21.             //选择向右走还是向下走
    22.             dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
    23.             if (dp[i][j] <= 0) {
    24.                 dp[i][j] = 1;
    25.             }
    26.         }
    27.     }
    28.     return dp[0][0];
    29. }

    如果动态规划做的多的话，必不可少的一步就是空间复杂度可以进行优化，比如 5题，10题，53题，72题 ，115 题 等等都已经用过了。

    因为我们的 dp 数组在更新第 i 行的时候，我们只需要第 i+1 行的信息，而 i+2，i+3 行的信息我们就不再需要了，我们我们其实不需要二维数组，只需要一个一维数组就足够了。

    1. public int calculateMinimumHP(int[][] dungeon) {
    2.     int row = dungeon.length;
    3.     int col = dungeon[0].length;
    4.     int[] dp = new int[col + 1];
    5.  
    6.     for (int i = 0; i <= col; i++) {
    7.         dp[i] = Integer.MAX_VALUE;
    8.     }
    9.     dp[col - 1] = dungeon[row - 1][col - 1] > 0 ? 1 : -dungeon[row - 1][col - 1] + 1;
    10.     for (int i = row - 1; i >= 0; i--) {
    11.         for (int j = col - 1; j >= 0; j--) {
    12.             if (i == row - 1 && j == col - 1) {
    13.                 continue;
    14.             }
    15.             dp[j] = Math.min(dp[j], dp[j + 1]) - dungeon[i][j];
    16.             if (dp[j] <= 0) {
    17.                 dp[j] = 1;
    18.             }
    19.         }
    20.     }
    21.     return dp[0];
    22. }
  • 相关阅读:
    Java 请求华为云认证接口API
    科普数据库
    设计简单的起始页Jump
    在页面使用富文本编译器
    网页设计——个人简历
    java返回前端实体类json数据时忽略某个属性方法
    电视盒子什么品牌好？内行分享权威电视盒子品牌排行榜
    C++实现轻量级RPC分布式网络通信框架
    ingress相关yaml文件报错且相关资源一切正常解决方法
    【python】基于随机森林和决策树的鸢尾花分类
  • 原文地址：https://blog.csdn.net/kiugvui/article/details/136770852