LeetCode 174. 地下城游戏

2022-08-04 HGNULB 约 10 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 174. 地下城游戏

题意分析

骑士从左上角出发，每次只能向右或向下走一格，要走到右下角救出公主。每格有一个整数：正数是补血，负数是扣血。任何时刻血量降到 0 或以下，骑士立即死亡。问出发时最少需要多少初始血量。

「任何时刻」这四个字决定了这道题的全部难度。它意味着代价不是路径和这种可以自由累加的量，而是一个沿途必须处处满足的约束。同一条路径，如果先扣血再补血，和先补血再扣血，所需的初始血量完全不同——即便总和一样。

血量必须严格大于 0，也就是最小合法血量是 1。所以答案至少是 1，即使终点格子是个大补包也一样。

每格进入后血量立刻结算，包括起点格和终点格。起点格的数值要从初始血量里扣（或加），终点格同样要结算完才算通关。

数据规模是行列都不超过 200，格子数最多 4 万。这个规模允许 $O(mn)$ 的表格计算，也允许 $O(mn)$ 的空间，不需要滚动优化。

边界包括：只有一格的地牢；整条路径全是正数（答案 1）；终点是巨大的负数；以及起点就是负数导致初始血量必须先抬高。

解法：逆向动态规划

核心思路

先看为什么正向 DP 走不通。若定义「从起点走到 (i, j) 时的最大剩余血量」，会发现它无法决定后续——一条剩余血量高但中途曾濒死的路径，和一条剩余血量低但一路平稳的路径，未来的可行性没有可比性；而且「最大剩余血量」与「最小初始血量」这两个量需要同时最优，单个状态装不下。若定义成二元组再逐一比较，状态之间不存在全序，DP 的最优子结构就崩了。

换个方向看就顺了。定义 dp[i][j] 为「站在 (i, j) 这一格、且该格的数值尚未结算时，为了能安全走到终点，此刻至少需要多少血量」。这个定义的妙处在于它只依赖未来，与骑士是怎么走到这里的完全无关——路径历史被彻底剥离，无后效性成立。

转移是这样推出来的。站在 (i, j)，结算完本格后血量变成 h + dungeon[i][j]（h 是进入本格前的血量）。接下来要么向右走、要么向下走，因此结算后的血量必须不小于两个邻居所需的血量中的较小者（骑士会挑更省的那条走）。记 minNext = min(dp[i+1][j], dp[i][j+1])，则要求 $h + dungeon[i][j] \ge minNext$，即 $h \ge minNext - dungeon[i][j]$。

但还有一条硬约束：任何时刻血量必须至少为 1，所以 h 本身也不能小于 1。两条约束取较严者，得到 $dp[i][j] = \max(1,\ minNext - dungeon[i][j])$。这个 max(1, …) 正是「本格是大补包时不能靠负血量硬撑」的数学表达，缺了它整张表都会错。

计算顺序必须与依赖一致：dp[i][j] 依赖右边和下边，所以要从右下往左上递推，行倒着走、列也倒着走。

终点的边界用哨兵行列处理。给 DP 表多开一行一列并整体填成无穷大，再把终点右侧和下侧那两个哨兵位置成 1。这样计算终点格时 minNext 自然等于 1，公式统一成 $\max(1, 1 - dungeon[m-1][n-1])$，不需要为终点单写一段特判。其余哨兵位保持无穷大，代表「不可通行」，在取最小值时会被自动排除。

答案是 dp[0][0]——站在起点、起点格尚未结算时所需的血量，正是初始血量。

解题步骤

开一张 (m+1) × (n+1) 的表并全部填成一个极大值。多出的一行一列是哨兵，极大值表示「往这个方向走不通」，在后续取最小值时自然落选，省掉所有越界判断。

把 dp[m][n-1] 与 dp[m-1][n] 置为 1。这两个位置分别是终点的正下方和正右方，置 1 表示「通关后只要还剩 1 点血就算成功」。只能置这两个，其他哨兵位必须保持极大值；多置会让某些非法方向变得可行。

双层循环都从大到小：外层 i 从 m-1 递减到 0，内层 j 从 n-1 递减到 0。方向必须与依赖一致，任何一层写成递增，都会在用到右侧或下侧状态时读到未计算的初值。

取右侧与下侧的较小值 minNext。取最小而不是最大，因为骑士可以自由选择走哪条，当然挑需求更低的那条。

写入 $dp[i][j] = \max(1, minNext - dungeon[i][j])$。减号方向要想清楚：本格是正数（补血）时需求下降，是负数（扣血）时需求上升，所以是减去格子的值。外层的 max(1, …) 保证血量下限，绝不能省。

返回 dp[0][0]，注意不是 dp[m-1][n-1]——本题的答案在起点。

以 dungeon = [[-2, -3, 3], [-5, -10, 1], [10, 30, -5]] 走一遍，预期答案 7。

从右下角开始。dp[2][2] = \max(1, 1 - (-5)) = 6：站在终点前需要 6 点血，扣掉 5 还剩 1。

第 2 行继续向左。dp[2][1]：右邻是 6、下邻是哨兵极大值，minNext = 6，$\max(1, 6 - 30) = 1$——本格补 30 血，需求被压到下限 1。dp[2][0]：右邻是 1、下邻是极大值，minNext = 1，$\max(1, 1 - 10) = 1$。

第 1 行。dp[1][2]：下邻是 6、右邻是哨兵极大值，minNext = 6，$\max(1, 6 - 1) = 5$。dp[1][1]：下邻 dp[2][1] = 1、右邻 dp[1][2] = 5，minNext = 1，$\max(1, 1 - (-10)) = 11$。dp[1][0]：下邻 dp[2][0] = 1、右邻 dp[1][1] = 11，minNext = 1，$\max(1, 1 - (-5)) = 6$。

第 0 行。dp[0][2]：下邻 dp[1][2] = 5、右邻是哨兵，minNext = 5，$\max(1, 5 - 3) = 2$。dp[0][1]：下邻 dp[1][1] = 11、右邻 dp[0][2] = 2，minNext = 2，$\max(1, 2 - (-3)) = 5$。dp[0][0]：下邻 dp[1][0] = 6、右邻 dp[0][1] = 5，minNext = 5，$\max(1, 5 - (-2)) = 7$。

返回 7。验证最优路径「右 → 右 → 下 → 下」：初始 7 血，进入 -2 剩 5，进入 -3 剩 2，进入 3 变 5，进入 1 变 6，进入 -5 剩 1，全程未跌破 1，通关。若初始只有 6 血，同一路径到终点扣掉 5 后会变成 0，当场死亡；而 DP 已比较了每格向右、向下的全部选择，因此不存在需求更低的其他路径，7 即为最小值。

顺带看一眼 max(1, …) 的作用：dp[2][1] 处若写成 minNext - dungeon，会得到 -24，这个负值传到 dp[2][0] 会变成 $-24 - 10 = -34$，一路把整张表拖成负数，最终 dp[0][0] 会给出一个远小于 7 甚至为负的答案。

代码实现

import java.util.Arrays;

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)$，每个格子只被计算一次，格内只做一次取最小、一次减法和一次取最大。$200 \times 200 = 4 \times 10^4$ 次运算，远低于时限。

空间复杂度：$O(mn)$，DP 表比原矩阵多一行一列。

关键点总结

当代价是「路径上处处必须满足的约束」而非「可自由累加的总量」时，正向 DP 往往因为需要同时最优两个量而失效。这类信号一出现，先试反向定义状态——让状态只依赖未来，路径历史自然被剥离。

状态定义要精确到「本格是否已结算」。本题定义为「进入该格前所需的血量」，若含糊成「在该格时的血量」，转移里的加减号会立刻混乱。

max(1, …) 不是防御性编程，而是题目「血量必须为正」这条硬约束的直接编码。凡是题面出现「不得低于某个阈值」，都要在转移里显式截断。

取邻居的最小值体现的是「走法由我选」，取最大值则会变成「必须两条路都能走通」。最优化方向由「谁做决策」决定，是 DP 转移里最容易搞反的一处。

哨兵行列配合极大值初值，能把边界情况折叠进主循环。要点是只把真正合法的出口置成有效值，其余保持极大值以自动落选。

易错点总结

错误写法：省略 max(1, …)，直接写 dp[i][j] = minNext - dungeon[i][j]。用例 dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]] → dp[2][1] 算成 -24 并一路传播，dp[0][0] 得到负数，正确答案是 7。

错误写法：把下限写成 max(0, …)。用例 dungeon = [[0]] → 算出 0，但血量为 0 即死亡，正确答案是 1。

错误写法：转移写成 minNext + dungeon[i][j]。用例 dungeon = [[-5]] → 算出 $\max(1, 1 + (-5)) = 1$，正确答案是 6。

错误写法：取邻居的最大值而非最小值。用例 dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]] → dp[1][1] 会用 dp[1][2] = 5 而不是 dp[2][1] = 1，需求被高估，最终答案大于 7。

错误写法：循环方向写成从左上往右下。用例 dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]] → 计算 dp[0][0] 时右邻与下邻都还是极大值初值，minNext 为极大值，结果溢出或给出一个荒谬的巨大数。

错误写法：哨兵行列全部置 1 而不是极大值。用例 dungeon = [[-2,-100]]：算起点时下方哨兵 1 会被当成可走出口，错误返回 3；实际必须继续经过右侧的 -100，正确答案是 103。

错误写法：终点右侧和下侧都忘记置 1。用例 dungeon = [[-5]]：终点的两个后继都保持无穷大，无法建立「通关后至少剩 1 点血」这个边界，结果会是极大值而非正确的 6。

错误写法：返回 dp[m-1][n-1]。用例 dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]] → 返回 6，正确答案是 7；本题的答案在起点而非终点。

错误写法：哨兵紧贴整数上界且错误边界让它参与减法。用例 dungeon = [[-5]] 且两个出口都未置 1：Integer.MAX_VALUE - (-5) 会溢出为负数，随后被截成 1，反而伪装成合法答案；使用留有余量的 1 << 30 仍不能替代正确初始化，但能避免错误静默变成小正数。

错误写法：正向定义状态为「从起点到 (i,j) 的最大剩余血量」。用例 dungeon = [[1, -3, 3], [0, -2, 0], [-3, -3, -3]] → 剩余血量最大的路径未必是初始血量最小的路径，两个目标无法用单一状态同时最优，得到的答案与正确值 3 不符。

相似题目

题目	难度	考察点
64. 最小路径和	中等	代价可自由累加，正向 DP 即可，是本题去掉「处处非负」约束后的基础形态
62. 不同路径	中等	计数而非最优化，转移是相加，展示同一网格骨架承载不同语义
63. 不同路径 II	中等	在计数基础上加障碍物，重点是把不可达状态置 0 而非用哨兵极大值
120. 三角形最小路径和	中等	同样可以自底向上递推来省掉边界特判，是「反向递推更简洁」的轻量版
931. 下降路径最小和	中等	每行可从上一行三个位置转移，考察边界列的处理而非状态定义
1594. 矩阵的最大非负积	中等	因为负负得正，必须同时维护最大与最小两个状态，是「单状态装不下」的另一形态
1289. 下降路径最小和 II	困难	约束是相邻行不能同列，需要维护每行最小与次小值把转移从 $O(n)$ 压到 $O(1)$
剑指 Offer 47. 礼物的最大价值	中等	与 64 同构的求最大值版本，适合先在这里练熟网格 DP 的滚动数组写法