地下城游戏 图解题解

地下城游戏这道题到底要求什么

题面这张 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、即活着进来即可，漏了它整张表基准就塌。最后别手滑改回正着推，后面的路没算根本得不出答案。

Python

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]

C++

int calculateMinimumHP(vector<vector<int>>& d){
    int m = d.size(), n = d[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    for(int i=m-1;i>=0;i--)
        for(int j=n-1;j>=0;j--){
            int nxt;
            if(i==m-1 && j==n-1) nxt = 1;
            else if(i==m-1) nxt = dp[i][j+1];
            else if(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 - d[i][j]);
        }
    return dp[0][0];
}

Java

int calculateMinimumHP(int[][] d){
    int m = d.length, n = d[0].length;
    int[][] dp = new int[m][n];
    for(int i=m-1;i>=0;i--)
        for(int j=n-1;j>=0;j--){
            int nxt;
            if(i==m-1 && j==n-1) nxt = 1;
            else if(i==m-1) nxt = dp[i][j+1];
            else if(j==n-1) nxt = dp[i+1][j];
            else nxt = Math.min(dp[i+1][j], dp[i][j+1]);
            dp[i][j] = Math.max(1, nxt - d[i][j]);
        }
    return dp[0][0];
}