企业官网建设流程全解析

深度解读 LeetCode 174 Dungeon Game：Go 逆向动态规划与二分搜索双解法

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

《Dungeon Game》（地下城游戏）是 LeetCode 上经典的二维网格动态规划题目：骑士从左上角出发营救右下角的公主，每个房间会扣血或补血，要求计算保证骑士全程血量不低于 1 的最小初始生命值。本篇文章以 LeetCode-Go 仓库中 0174.Dungeon-Game 题解目录 为主体，完整继承官方文档中的两种解法思路（从终点逆推的动态规划、二分搜索 + 可行性 DP），并结合仓库内的 Go 源码与单元测试做逐行拆解，帮助读者真正吃透这类"带约束的最短路"问题的状态设计，并掌握可直接复用的 Go 模板。

一、问题描述

恶魔抓住了公主P，把她囚禁在地下城（M × N 个房间组成的二维网格）的右下角。骑士K从左上角出发，必须穿过地下城、击败恶魔救出公主。

• 骑士的初始生命值是一个正整数；一旦某时刻生命值降到 0 或以下，他会立即死亡。
• 每个房间有一个整数值：
  • 负整数：房间由恶魔守卫，进入后扣除等量的生命值；
  • 0：空房间，不影响生命值；
  • 正整数：房间里有魔法球，进入后恢复等量的生命值。
• 为了尽快到达公主，骑士每步只能向右或向下移动一格。
• 要求：编写函数，计算骑士能够救出公主所需的最小初始生命值。

题目给出的经典示例：给定如下地下城，骑士若沿最优路径RIGHT -> RIGHT -> DOWN -> DOWN前进，初始生命值至少为7。

-2 -3 3 -5 -10 1 10 30 -5

两条注意事项：

• 骑士的生命值没有上限；
• 任意房间（包括左上角起点房间和右下角公主所在房间）都可能带来威胁（扣血）或增益（补血）。

二、题意提炼：把"游戏规则"翻译成算法约束

把游戏规则抽象为算法语言，核心约束有三条：

1. 网格即加权路径：从(0,0)走到(m-1,n-1)，只能向右/向下，路径上的每个格子值会直接加减骑士的剩余生命值；
2. 存活约束：进入任意格子后，骑士的剩余生命值必须≥ 1，否则死亡；
3. 起点终点都生效：进入(0,0)那一刻就会扣除/恢复生命，因此初始血量本身就要抵消掉起点的消耗；终点(m-1,n-1)的扣血同样必须扛住。

换句话说，题目本质是：在所有从左上到右下的单调路径中，找到一条"沿途最低剩余血量"最高的路径，并以此反推出所需的初始血量。

为什么不能直接正向做贪心或普通 DP？

一个直觉误区是"每条路径上累计扣血最少的路径就是最优路径"。但生命值约束是路径上的瓶颈（minimum 而非 sum）：某条路径总扣血更少，但如果它在中间某一段把骑士血量压到接近 1，后续遇到大扣血房间就会死；而另一条总扣血较多的路径，可能因为中途有补血房间而全程存活。因此不能贪心，必须枚举/搜索所有路径的"最低点"。

三、解法一：从终点逆推的动态规划（推荐）

3.1 核心思想：逆向 DP

正向思考时，路径的"当前剩余血量"依赖于此前走过的路，不满足无后效性。官方题解（见 website/content.en/ChapterFour/0100~0199/0174.Dungeon-Game.md）采用的策略是从终点向起点逆推：

定义dp[i][j]为骑士进入坐标为(i,j)的格子之前所需的最小生命值。逆推方向正好与移动方向相反：既然骑士只能向右、向下走，那么逆推时只需要关心下一行(i+1,j)和右一列(i,j+1)两个格子。

3.2 初始化：终点的边界条件

先看终点(m-1, n-1)。进入终点前需要dp[m-1][n-1]，进入后剩余生命为dp[m-1][n-1] + dungeon[m-1][n-1]，必须同时满足：

• 存活条件：dp[m-1][n-1] + dungeon[m-1][n-1] ≥ 1
• 自身为正：dp[m-1][n-1] ≥ 1

两个不等式方向相同，取交集后起决定作用的是数轴上最右侧的值：

dp[m-1][n-1] = max(1 - dungeon[m-1][n-1], 1)

边界行与边界列：最后一行的格子只能从右侧过来（dp[m-1][i+1]），最后一列的格子只能从下方过来（dp[i+1][n-1]），因此可以先行独立推出：

dp[m-1][i] = max(1, dp[m-1][i+1] - dungeon[m-1][i]) // i 从 n-2 到 0 dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1]) // i 从 m-2 到 0

至此 DP 的初始条件全部就绪。

3.3 状态转移方程的推导

对一般位置(i,j)，dp[i][j]与dp[i+1][j]、dp[i][j+1]相关：dp[i][j]扣除本格子的血量后，至少要能满足下一行和右一列格子的最低血量要求，同时自身血量 ≥ 1。于是得到两组不等式：

dp[i][j] + dungeon[i][j] ≥ dp[i+1][j] 且 dp[i][j] ≥ 1 （满足下一行格子的最低血量） dp[i][j] + dungeon[i][j] ≥ dp[i][j+1] 且 dp[i][j] ≥ 1 （满足右一列格子的最低血量）

分别化简：

• 第一式 ⇒dp[i][j] = max(1, dp[i+1][j] - dungeon[i][j])（走"下"这条路所需血量）
• 第二式 ⇒dp[i][j] = max(1, dp[i][j+1] - dungeon[i][j])（走"右"这条路所需血量）

两条路都可行，取更小者即为当前格子的最小需求，最终状态转移方程：

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

DP 完成后，dp[0][0]即骑士的最小初始生命值。

3.4 Go 实现（对应仓库源码）

仓库源码见 174. Dungeon Game.go，与官方文档代码一致：

package leetcode import "math" // 解法一 动态规划 func calculateMinimumHP(dungeon [][]int) int { if len(dungeon) == 0 { return 0 } m, n := len(dungeon), len(dungeon[0]) dp := make([][]int, m) for i := 0; i < m; i++ { dp[i] = make([]int, n) } dp[m-1][n-1] = max(1-dungeon[m-1][n-1], 1) for i := n - 2; i >= 0; i-- { dp[m-1][i] = max(1, dp[m-1][i+1]-dungeon[m-1][i]) } for i := m - 2; i >= 0; i-- { dp[i][n-1] = max(1, dp[i+1][n-1]-dungeon[i][n-1]) } for i := m - 2; i >= 0; i-- { for j := n - 2; j >= 0; j-- { dp[i][j] = min(max(1, dp[i][j+1]-dungeon[i][j]), max(1, dp[i+1][j]-dungeon[i][j])) } } return dp[0][0] } func max(a int, b int) int { if a > b { return a } return b } func min(a int, b int) int { if a > b { return b } return a }

代码细节说明：

• 空数组保护：len(dungeon) == 0时直接返回 0；
• 逆推遍历：先填终点，再分别从右到左填最后一行、从下到上填最后一列，最后按i从m-2到0、j从n-2到0的顺序填内部格子；
• 两处max(1, ...)正是前面推导出的"自身血量 ≥ 1"约束，min则是两种走法中取较优。

复杂度：时间复杂度 O(m·n)，空间复杂度 O(m·n)。

3.5 手动推演：为什么答案是 7

用上面方程手工推演官方示例{{-2,-3,3},{-5,-10,1},{10,30,-5}}，验证正确性：

1. 终点：dp[2][2] = max(1-(-5), 1) = 6
2. 最后一行：dp[2][1] = max(1, 6-30) = 1；dp[2][0] = max(1, 1-10) = 1
3. 最后一列：dp[1][2] = max(1, 6-1) = 5；dp[0][2] = max(1, 5-3) = 2
4. 内部格子：
   • dp[1][1] = min(max(1,5+10), max(1,1+10)) = min(15, 11) = 11
   • dp[1][0] = min(max(1,11+5), max(1,1+5)) = min(16, 6) = 6
   • dp[0][1] = min(max(1,2+3), max(1,11+3)) = min(5, 14) = 5
   • dp[0][0] = min(max(1,5+2), max(1,6+2)) = min(7, 8) = 7

dp[0][0] = 7，与题目给出的答案一致。这也验证了"总扣血更少"的路径（向右走到(0,1)再往下，对应dp[0][1]分支）反而不是最优：因为(0,0)->(0,1)方向虽然最终只需 5，但受制于(1,0)分支只需 6 更小，而 7 是两条路综合后从(0,0)出发所需的最小值。

四、解法二：二分搜索 + 可行性 DP

4.1 思路：把"求最小初始血量"转化为"判定性问题"

骑士初始血量取值范围一定在[1, +∞)内（文档中记为[1，+∞)）。因此可以二分这个区间：

• 取中间值mid作为初始血量；
• 在网格上做一次正向 DP（canCross），判定该血量能否活着走到终点；
• 若能到达，则缩小搜索空间至[1, mid]（尝试更小的血量）；
• 若不能到达，则搜索空间变为[mid+1, +∞)（血量必须更大）。

当low == high时，low就是最小可行初始血量。这一思想将"优化问题"转成了"判定问题"，配合单调性（血量越大越容易通过）即可二分。

4.2 canCross：正向可行性 DP

canCross维护dp[i][j]为以给定初始血量start出发、走到(i,j)时剩余的最大生命值，并且只接受"上一步之后血量 > 0"的转移：

func canCross(dungeon [][]int, start int) bool { m, n := len(dungeon), len(dungeon[0]) dp := make([][]int, m) for i := 0; i < m; i++ { dp[i] = make([]int, n) } for i := 0; i < len(dp); i++ { for j := 0; j < len(dp[i]); j++ { if i == 0 && j == 0 { dp[i][j] = start + dungeon[0][0] } else { a, b := math.MinInt64, math.MinInt64 if i > 0 && dp[i-1][j] > 0 { a = dp[i-1][j] + dungeon[i][j] } if j > 0 && dp[i][j-1] > 0 { b = dp[i][j-1] + dungeon[i][j] } dp[i][j] = max(a, b) } } } return dp[m-1][n-1] > 0 }

三个关键点：

• 起点：dp[0][0] = start + dungeon[0][0]，初始血量先被起点格子结算一次；
• 转移合法性：只有当上一步剩余血量> 0（dp[i-1][j] > 0或dp[i][j-1] > 0）时才允许从该方向转移，否则该方向置为math.MinInt64，表示不可达；
• 判定标准：走到终点后剩余血量dp[m-1][n-1] > 0才视为存活（进入终点时血量必须 ≥ 1）。

4.3 二分主流程的 Go 实现

// 解法二 二分搜索 func calculateMinimumHP1(dungeon [][]int) int { low, high := 1, math.MaxInt64 for low < high { mid := low + (high-low)>>1 if canCross(dungeon, mid) { high = mid } else { low = mid + 1 } } return low }

细节说明：

• 下界low = 1（骑士初始生命必须是正整数，且至少要能扛过起点格子的结算）；
• 上界high = math.MaxInt64，对应文档中"骑士血量无上限"的设定；
• mid := low + (high-low)>>1为经典的防溢出二分中点写法；
• 二分的单调性依据：若初始血量mid可行，则任何≥ mid的血量都可行，因此可以安全收缩上界。

复杂度：每次判定 O(m·n)，二分迭代约log(math.MaxInt64)≈ 63 次，总时间复杂度 O(m·n·log MaxInt64)，空间复杂度 O(m·n)。

五、源码与测试验证

5.1 仓库文件结构

本题相关文件全部位于 leetcode/0174.Dungeon-Game 目录：

• 174. Dungeon Game.go：两种解法的完整 Go 实现（含max/min工具函数）；
• 174. Dungeon Game_test.go：表驱动单元测试；
• README.md：中文版题解文档，与 website/content.en/ChapterFour/0100~0199/0174.Dungeon-Game.md 互为镜像。

5.2 测试用例与预期结果

测试文件174. Dungeon Game_test.go中覆盖了四组用例加一个空输入边界，均同时验证calculateMinimumHP与calculateMinimumHP1：

其中最后一组正是题目经典示例；{{100}}说明"起点就是补血房间"时初始血量只需 1；{{-3, 5}}这类 1×2 边界则验证了仅一行时的行内逆推逻辑。测试对两种解法都断言了相同答案，可以作为双解法的交叉验证。

5.3 如何运行测试

仓库根目录 go.mod 声明的模块名为github.com/halfrost/LeetCode-Go（Go 1.19），并对structures、template等子包配置了本地replace，因此在仓库根目录直接运行即可：

# 仅运行本题测试 go test -v ./leetcode/0174.Dungeon-Game/... # 运行全部题解测试并生成覆盖率 go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

第二条命令与仓库 gotest.sh 的逻辑一致：go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...，一次性对全部包生成合法的覆盖率文件。

六、总结：两类解法的适用场景

这道题最有价值的地方在于状态设计的方向选择：当"走到某格时的剩余血量"受历史路径影响、正向 DP 不满足无后效性时，转而在"进入该格之前需要多少血量"这个视角下逆推，就能把约束变成简洁的局部转移方程。这一范式在最小/最大路径血量、带存活约束的寻路类题目中非常通用，值得反复体会。

（本文内容以 LeetCode-Go 仓库的题解文档与源码为事实依据，示例推演、复杂度分析与测试用例均可对照仓库文件复核。）

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go