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

深度解读 LeetCode 174 Dungeon GameGo 逆向动态规划与二分搜索双解法【免费下载链接】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两条注意事项骑士的生命值没有上限任意房间包括左上角起点房间和右下角公主所在房间都可能带来威胁扣血或增益补血。二、题意提炼把游戏规则翻译成算法约束把游戏规则抽象为算法语言核心约束有三条网格即加权路径从(0,0)走到(m-1,n-1)只能向右/向下路径上的每个格子值会直接加减骑士的剩余生命值存活约束进入任意格子后骑士的剩余生命值必须≥ 1否则死亡起点终点都生效进入(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)的格子之前所需的最小生命值。逆推方向正好与移动方向相反既然骑士只能向右、向下走那么逆推时只需要关心下一行(i1,j)和右一列(i,j1)两个格子。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][i1]最后一列的格子只能从下方过来dp[i1][n-1]因此可以先行独立推出dp[m-1][i] max(1, dp[m-1][i1] - dungeon[m-1][i]) // i 从 n-2 到 0 dp[i][n-1] max(1, dp[i1][n-1] - dungeon[i][n-1]) // i 从 m-2 到 0至此 DP 的初始条件全部就绪。3.3 状态转移方程的推导对一般位置(i,j)dp[i][j]与dp[i1][j]、dp[i][j1]相关dp[i][j]扣除本格子的血量后至少要能满足下一行和右一列格子的最低血量要求同时自身血量 ≥ 1。于是得到两组不等式dp[i][j] dungeon[i][j] ≥ dp[i1][j] 且 dp[i][j] ≥ 1 满足下一行格子的最低血量 dp[i][j] dungeon[i][j] ≥ dp[i][j1] 且 dp[i][j] ≥ 1 满足右一列格子的最低血量分别化简第一式 ⇒dp[i][j] max(1, dp[i1][j] - dungeon[i][j])走下这条路所需血量第二式 ⇒dp[i][j] max(1, dp[i][j1] - dungeon[i][j])走右这条路所需血量两条路都可行取更小者即为当前格子的最小需求最终状态转移方程dp[i][j] min( max(1, dp[i][j1] - dungeon[i][j]), max(1, dp[i1][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][i1]-dungeon[m-1][i]) } for i : m - 2; i 0; i-- { dp[i][n-1] max(1, dp[i1][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][j1]-dungeon[i][j]), max(1, dp[i1][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}}验证正确性终点dp[2][2] max(1-(-5), 1) 6最后一行dp[2][1] max(1, 6-30) 1dp[2][0] max(1, 1-10) 1最后一列dp[1][2] max(1, 6-1) 5dp[0][2] max(1, 5-3) 2内部格子dp[1][1] min(max(1,510), max(1,110)) min(15, 11) 11dp[1][0] min(max(1,115), max(1,15)) min(16, 6) 6dp[0][1] min(max(1,23), max(1,113)) min(5, 14) 5dp[0][0] min(max(1,52), max(1,62)) min(7, 8) 7dp[0][0] 7与题目给出的答案一致。这也验证了总扣血更少的路径向右走到(0,1)再往下对应dp[0][1]分支反而不是最优因为(0,0)-(0,1)方向虽然最终只需 5但受制于(1,0)分支只需 6 更小而 7 是两条路综合后从(0,0)出发所需的最小值。四、解法二二分搜索 可行性 DP4.1 思路把求最小初始血量转化为判定性问题骑士初始血量取值范围一定在[1, ∞)内文档中记为[1∞)。因此可以二分这个区间取中间值mid作为初始血量在网格上做一次正向 DPcanCross判定该血量能否活着走到终点若能到达则缩小搜索空间至[1, mid]尝试更小的血量若不能到达则搜索空间变为[mid1, ∞)血量必须更大。当low high时low就是最小可行初始血量。这一思想将优化问题转成了判定问题配合单调性血量越大越容易通过即可二分。4.2 canCross正向可行性 DPcanCross维护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]初始血量先被起点格子结算一次转移合法性只有当上一步剩余血量 0dp[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输入 dungeon预期输出{{2, 1}, {1, -1}}1{{-3, 5}}4{{100}}1{{-2, -3, 3}, {-5, -10, 1}, {10, 30, -5}}7空切片[][]int{}0其中最后一组正是题目经典示例{{100}}说明起点就是补血房间时初始血量只需 1{{-3, 5}}这类 1×2 边界则验证了仅一行时的行内逆推逻辑。测试对两种解法都断言了相同答案可以作为双解法的交叉验证。5.3 如何运行测试仓库根目录 go.mod 声明的模块名为github.com/halfrost/LeetCode-GoGo 1.19并对structures、template等子包配置了本地replace因此在仓库根目录直接运行即可# 仅运行本题测试 go test -v ./leetcode/0174.Dungeon-Game/... # 运行全部题解测试并生成覆盖率 go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...第二条命令与仓库 gotest.sh 的逻辑一致go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...一次性对全部包生成合法的覆盖率文件。六、总结两类解法的适用场景维度解法一逆向 DP解法二二分搜索 可行性 DP核心思想从终点逆推直接算出每个格子所需的最小进入血量二分初始血量正向 DP 判定可行性时间复杂度O(m·n)O(m·n·log MaxInt64)空间复杂度O(m·m)O(m·n)O(m·n)工程取舍一次遍历直接出答案推荐首选思路直观、可复用可行性判定模板但常数更大这道题最有价值的地方在于状态设计的方向选择当走到某格时的剩余血量受历史路径影响、正向 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考