地下城游戏

下面 15 步动画会按主解代码推进，而不是泛泛讲题型。

1. 看输入：3×3 地下城：地下城是 3 行 3 列。骑士从左上 (0,0) 走到右下 (2,2) 救公主，每格的数字会加到血量上：负数扣血、正数回血。全程血量必须保持大于 0。

2. dp 的含义：进入该格所需最低血量：我们要填的不是地下城原值，而是 dp 表：dp[r][c] 表示骑士进入格子 (r,c) 之前至少要带多少血，才能活着走完后面的路。最终答案就是 dp[0][0]。

3. 为什么倒着填：从起点正推，必须同时记住走过的路径和路上的最低血，很难。倒着从终点推：进入某格前的需求，只由它右边、下边两格的需求决定。所以从右下角 (2,2) 开始填。

4. 填 dp[2][2]：终点格：终点 (2,2) 没有右格和下格，约定它的出口需求是 1。本格 dungeon 为 −5，会扣 5 血，所以 need = 1 − (−5) = 6。dp[2][2] = max(1,6) = 6。

5. 填 dp[2][1]：(2,1) 右边是 dp[2][2]=6（蓝色依赖格）。本格 dungeon=30 回血很多，need = 6 − 30 = −24，是负的；血量至少为 1，所以 dp[2][1] = max(1,−24) = 1。

6. 填 dp[2][0]：底行填完：(2,0) 右边是 dp[2][1]=1。本格 dungeon=10 回血，need = 1 − 10 = −9，取 max(1,−9)=1。底行 dp = [1,1,6] 填完。

7. 填 dp[1][2]：(1,2) 下边是 dp[2][2]=6。本格 dungeon=1，need = 6 − 1 = 5，dp[1][2] = max(1,5) = 5。

8. 填 dp[1][1]：取右、下较小者：(1,1) 右边 dp[1][2]=5、下边 dp[2][1]=1，取较小的 1。本格 dungeon=−10 扣 10 血，need = 1 − (−10) = 11。dp[1][1] = max(1,11) = 11。

9. 填 dp[1][0]：中行填完：(1,0) 右边 dp[1][1]=11、下边 dp[2][0]=1，取较小的 1。本格 dungeon=−5，need = 1 − (−5) = 6。dp[1][0] = max(1,6) = 6。中行 dp = [6,11,5] 填完。

10. 填 dp[0][2]：(0,2) 下边是 dp[1][2]=5。本格 dungeon=3 回血，need = 5 − 3 = 2，dp[0][2] = max(1,2) = 2。

11. 填 dp[0][1]：(0,1) 右边 dp[0][2]=2、下边 dp[1][1]=11，取较小的 2。本格 dungeon=−3，need = 2 − (−3) = 5。dp[0][1] = max(1,5) = 5。

12. 填 dp[0][0]：起点：起点 (0,0) 右边 dp[0][1]=5、下边 dp[1][0]=6，取较小的 5。本格 dungeon=−2，need = 5 − (−2) = 7。dp[0][0] = max(1,7) = 7。整张 dp 表填满。

13. 读出答案：dp[0][0] = 7，意思是骑士出发时至少要带 7 点血。返回 7。

14. 验证这条最优路：带 7 血走 (0,0)→(0,1)→(0,2)→(1,2)→(2,2)：7−2=5，5−3=2，2+3=5，5+1=6，6−5=1，每一步血量都大于 0。这正是 dp 选出的最省路线。

15. 复杂度与要点：整张表 m×n 个格子，每格只用右、下两个已算好的值算一次，时间 O(mn)、空间 O(mn)。核心三步：倒着填、取右下较小需求、再用 max(1, …) 兜住血量下限。

记住这题的代码骨架：题意约束先落到状态变量，再用循环或递归维护它。