LeetCode 174. 地下城游戏

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 字节
标签
数组 动态规划 矩阵

题目描述

✅ 174. 地下城游戏

image-20260929090833618

image-20260929090833767

题意分析

从左上角出发，每次只能向右或向下，最终到达右下角。进入每个格子立即按其数值增减血量，起点和终点也要结算；任何时刻血量降到 0 或以下都会失败。要求进入起点之前最少需要多少血量。

解法：逆向动态规划

核心思路

[!blue]
倒推每个位置进入前的最低血量，而不是只计算整条路径的总收益。 总收益足够不代表沿途没有提前死亡。定义 dp[i][j] 为尚未结算当前格子时，为了从这里安全走到终点所需的最少血量，它已经包含未来每一步的存活要求。

从当前格子可以去右边或下面，选后继需求更小的一条路，令 minNext = min(dp[i][j+1], dp[i+1][j])。若进入当前格子前有 h 点血，结算后就有 h+dungeon[i][j]，它必须不少于 minNext，同时进入前也必须满足 h>=1。

两个条件合起来就是 dp[i][j] = max(1, minNext-dungeon[i][j])。这个血量既能活着进入当前格子，也能在结算后达到所选后继的最低要求；再少则会违反其中一个条件，所以它恰好是最小值。扣血格提高进入需求，补血格降低进入需求，但不能降到 0。

终点结算后只需剩下至少 1 点血，因此其需求是 max(1,1-dungeon[m-1][n-1])。代码多开一行一列，把终点下方和右方的虚拟后继设为 1，使终点也能使用同一转移；其他越界位置设为极大值，表示不能从那里离开地牢。

解题步骤

  1. 创建 (m+1)×(n+1) 的状态表并初始化为极大值，只令 dp[m][n-1] 与 dp[m-1][n] 为 1。
  2. 行从下往上、列从右往左枚举，保证右侧和下侧状态已经计算完成。
  3. 取两个后继需求的较小值，减去本格数值，再与 1 取最大，写入当前状态。
  4. 返回 dp[0][0]，即进入起点前的最低血量。

单格地牢直接使用终点公式。只有一行或一列时，非法方向的极大值会让转移自动选择唯一合法方向；即使所有格子都能补血，初始血量也至少为 1。

代码实现

class Solution {

    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;

        // 多开一行一列哨兵，inf 表示该方向走不通。
        int[][] dp = new int[m + 1][n + 1];
        int inf = 1 << 30;

        for (int i = 0; i <= m; i++) {
            Arrays.fill(dp[i], inf);
        }

        // 终点的下方与右方置 1：通关后留 1 点血即可。
        dp[m][n - 1] = 1;
        dp[m - 1][n] = 1;

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

                // max(1, ...) 保证任何时刻血量不低于 1。
                dp[i][j] = Math.max(1, minNext - dungeon[i][j]);
            }
        }

        return dp[0][0];
    }
}

func calculateMinimumHP(dungeon [][]int) int {
    m, n := len(dungeon), len(dungeon[0])

    // 多开一行一列哨兵，inf 表示该方向走不通。
    const inf = 1 << 30
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
        for j := range dp[i] {
            dp[i][j] = inf
        }
    }

    // 终点的下方与右方置 1：通关后留 1 点血即可。
    dp[m][n-1] = 1
    dp[m-1][n] = 1

    for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 0; j-- {
            minNext := min(dp[i+1][j], dp[i][j+1])
            // max(1, ...) 保证任何时刻血量不低于 1。
            dp[i][j] = max(1, minNext-dungeon[i][j])
        }
    }

    return dp[0][0]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

  • 时间复杂度：$O(mn)$，每格计算一次。
  • 空间复杂度：$O(mn)$，保存带边界的状态表。

关键点总结

[!green]

  • 状态定义在本格结算之前。
  • 负格提高需求，正格降低需求，但不能低于一。
  • 可以自主选择路线，所以后继需求取较小值。

易错点总结

[!yellow]

  • 下限写成零：零血量已经死亡。
  • 将本格数值加到需求上：补血与扣血的影响被反转。
  • 所有边界都设为一：允许未到终点就从边缘退出。
  • 返回终点状态：答案应是进入起点前的需求。

相似题目

题目 难度 关联与区别
64. 最小路径和 中等 同样在网格路径上DP，原题最小化累计代价，本题还要求每个前缀生命值为正，需从终点反推最低需求。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/97652987
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！