题目描述
思路解析
一句话答案：LeetCode 174 地下城游戏：骑士从左上走到右下、全程血量至少剩 1，求最低初始血量。正着推剩血兜不住后路，改从右下往左上倒推，dp[i][j]=max(1, min(右,下)−本格)，时间 O(m×n)、空间 O(m×n)。
地下城游戏这道题到底要求什么
题面这张 4×5 网格是 [[-2,-3,3,-5,1],[-5,-10,1,-2,-3],[10,30,-5,4,-1],[1,-7,2,-3,2]]，负数是恶魔进去扣血，正数是药水进去回血。骑士从左上出发，每步只能向右或向下走到右下角救公主，全程血量任何时刻都不能掉到 0、至少剩 1 滴。问出发最少带多少血，答案是 6。
为什么把每条走法都试一遍行不通
从左上到右下、每步只能右或下，一条走法就是若干个「右」「下」的排列，走法数是组合数级，网格一大就指数级膨胀，一条条试跑不动。不同走法中间大段重叠，子网格被反复重算。所以把「从某格走到终点」这类子问题算一次存起来复用，正是动态规划（把『从某格活到终点至少要带多少血』存下来不重算）的用武之地。
为什么从左上角正着往下推会算错
顺题意会想从起点往终点推，记「走到每格时还剩多少血」。可这里有撕扯：到某格，你既想让花掉的初始血最少，又想让剩的血最多，两个目标打架。选初始血更省的来路，剩血反而可能更少，往后撑不住，而站在这格根本不知道后面要扣多少血。
动态规划能立住靠的是无后效性（一个状态定下来后，后面怎么走只取决于这状态本身，跟怎么到这儿无关）；正着推时「还剩多少血」管不住后面未知的需求，无后效性被打破，递推架不起来。
倒过来定义 dp，从右下角往回推
定义 dp[i][j] 表示「进入第 i 行第 j 列这格前，至少带多少血才能活到终点」，i、j 是行号、列号、从 0 数起。这个量只由它右下方那片子网格决定，跟怎么走到这格无关，无后效性回来了。
进入这格先按本格加减血，再迈进右、下两条后路里要求更低的那条 min(右, 下)。带进来的血抵掉本格增减后不能低于它，即 dp[i][j] ≥ min(右, 下) − 本格。人在本格也得活着、至少留 1 滴，于是 dp[i][j] = max(1, min(右, 下) − 本格)。终点没有后路，套成 max(1, 1 − 本格)。
拿题面示例从终点倒着填一遍
从右下角那格 (3,4) 起，它回血 2，进来前 max(1, 1−2)=1。末行末列只剩一条后路：末行倒数第二格 (3,3) 扣血 3，max(1, 1−(−3))=4。分叉格取两条后路里较小的：(2,3) 后路 4 和 2 挑 2，本格回血 4，2−4=−2 兜底成 1；(1,1) 后路 1 和 2 挑 1，本格扣血 10，1−(−10)=11。倒推到左上角起点 (0,0)，后路是下方 6、右方 4 挑 4，本格扣血 2，max(1, 4−(−2))=6，就是答案，和题面对上。
终点那格的基准差 1，倒推出的每一格为什么跟着偏小
每格只算一次，时间 O(m×n)；存整张 dp 表空间 O(m×n)，但算某格只用到右边和下边紧挨的值，可只留一行倒着覆盖，压到 O(n)。坑几乎全在边界：末列格子右边没格、末行格子下面没格，只能取那唯一一条后路，照搬 min 会读到越界值；终点那格背后无路，「后路要求」要当成 1、即活着进来即可，漏了它整张表基准就塌。最后别手滑改回正着推，后面的路没算根本得不出答案。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
思路一句话：后路里要求更低的 - 本格，再兜底≥1。dp[i][j] 是进入该格前要带的血。下面每格都套它，一步步演给你看。
核心直觉：需要的血量由「后面的路」决定，所以从终点倒推，而不是从起点正推。
终点 (3,4) 公主所在：到这里只要活着（血量 ≥1）即可。本格是 回血 2，要让进来后还剩 ≥1，进来前需要 max(1, 1-(2)) = 1。
末行 (3,3)：下面没格子，只能往右走。右边那格要求带 1 血，本格扣血 3，所以进本格前需要 max(1, 1-(-3)) = 4。
末行 (3,2)：下面没格子，只能往右走。右边那格要求带 4 血，本格回血 2，所以进本格前需要 max(1, 4-(2)) = 2。
末行 (3,1)：下面没格子，只能往右走。右边那格要求带 2 血，本格扣血 7，所以进本格前需要 max(1, 2-(-7)) = 9。
末行 (3,0)：下面没格子，只能往右走。右边那格要求带 9 血，本格回血 1，所以进本格前需要 max(1, 9-(1)) = 8。
末列 (2,4)：右边没格子，只能往下走。下面那格要求带 1 血，本格扣血 1，所以进本格前需要 max(1, 1-(-1)) = 2。
算 (2,3)：两条后路——往下 dp[3][3]=4（蓝），往右 dp[2][4]=2（蓝）。先挑要求更低的 2（走右边更省血）。
本格回血 4，能抵掉一部分需求：2-(4)=-2，不足 1 兜底成 1（人至少 1 滴血），填进 (2,3) = 1。
算 (2,2)：两条后路——往下 dp[3][2]=2（蓝），往右 dp[2][3]=1（蓝）。先挑要求更低的 1（走右边更省血）。
本格扣血 5，进来前得多攒：1-(-5)=6，填进 (2,2) = 6。
算 (2,1)：两条后路——往下 dp[3][1]=9（蓝），往右 dp[2][2]=6（蓝）。先挑要求更低的 6（走右边更省血）。
本格回血 30，能抵掉一部分需求：6-(30)=-24，不足 1 兜底成 1（人至少 1 滴血），填进 (2,1) = 1。
算 (2,0)：两条后路——往下 dp[3][0]=8（蓝），往右 dp[2][1]=1（蓝）。先挑要求更低的 1（走右边更省血）。
本格回血 10，能抵掉一部分需求：1-(10)=-9，不足 1 兜底成 1（人至少 1 滴血），填进 (2,0) = 1。
末列 (1,4)：右边没格子，只能往下走。下面那格要求带 2 血，本格扣血 3，所以进本格前需要 max(1, 2-(-3)) = 5。
算 (1,3)：两条后路——往下 dp[2][3]=1（蓝），往右 dp[1][4]=5（蓝）。先挑要求更低的 1（走下面更省血）。
本格扣血 2，进来前得多攒：1-(-2)=3，填进 (1,3) = 3。
算 (1,2)：两条后路——往下 dp[2][2]=6（蓝），往右 dp[1][3]=3（蓝）。先挑要求更低的 3（走右边更省血）。
本格回血 1，能抵掉一部分需求：3-(1)=2，填进 (1,2) = 2。
算 (1,1)：两条后路——往下 dp[2][1]=1（蓝），往右 dp[1][2]=2（蓝）。先挑要求更低的 1（走下面更省血）。
本格扣血 10，进来前得多攒：1-(-10)=11，填进 (1,1) = 11。
算 (1,0)：两条后路——往下 dp[2][0]=1（蓝），往右 dp[1][1]=11（蓝）。先挑要求更低的 1（走下面更省血）。
本格扣血 5，进来前得多攒：1-(-5)=6，填进 (1,0) = 6。
末列 (0,4)：右边没格子，只能往下走。下面那格要求带 5 血，本格回血 1，所以进本格前需要 max(1, 5-(1)) = 4。
算 (0,3)：两条后路——往下 dp[1][3]=3（蓝），往右 dp[0][4]=4（蓝）。先挑要求更低的 3（走下面更省血）。
本格扣血 5，进来前得多攒：3-(-5)=8，填进 (0,3) = 8。
算 (0,2)：两条后路——往下 dp[1][2]=2（蓝），往右 dp[0][3]=8（蓝）。先挑要求更低的 2（走下面更省血）。
本格回血 3，能抵掉一部分需求：2-(3)=-1，不足 1 兜底成 1（人至少 1 滴血），填进 (0,2) = 1。
算 (0,1)：两条后路——往下 dp[1][1]=11（蓝），往右 dp[0][2]=1（蓝）。先挑要求更低的 1（走右边更省血）。
本格扣血 3，进来前得多攒：1-(-3)=4，填进 (0,1) = 4。
算 (0,0)：两条后路——往下 dp[1][0]=6（蓝），往右 dp[0][1]=4（蓝）。先挑要求更低的 4（走右边更省血）。
本格扣血 2，进来前得多攒：4-(-2)=6，填进 (0,0) = 6。
表填满了。左上角 dp[0][0] = 6，就是骑士出发时必须带的最低血量——少一滴，某一步就会被恶魔打到 0 阵亡。
极端单格输入，正好检验 max(1, 1-本格) 这条终点公式。
两个高频追问，第一个直击「为什么倒推」。
参考代码
def calculateMinimumHP(dungeon): m, n = len(dungeon), len(dungeon[0]) dp = [[0]*n for _ in range(m)] for i in range(m-1, -1, -1): for j in range(n-1, -1, -1): if i == m-1 and j == n-1: nxt = 1 elif i == m-1: nxt = dp[i][j+1] elif j == n-1: nxt = dp[i+1][j] else: nxt = min(dp[i+1][j], dp[i][j+1]) dp[i][j] = max(1, nxt - dungeon[i][j]) return dp[0][0]复杂度
- 时间：O(m×n)，每格只算一次
- 空间：O(m×n)，存了整张表（可压成一行 O(n)）
易错点
面试追问把动画讲成自己的话
追问为什么不能用「最大路径和 / 最小扣血」那种正推思路？
追问能优化到 O(n) 空间吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
买卖股票的最佳时机 IV
LeetCode 188 · 困难 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题