深度剖析：地下城游戏

174. 地下城游戏

今天要介绍的是 地下城游戏。乍一看，这不就是 最小路径和 的变形嘛！！关于「最小路径和」的详细分析可见 浅析：最小路径和

在「最小路径和」中求的是最小值，而在「地下城游戏」中不就是找到一条和最大的路径嘛！！其实这样思考是错误的！！下面看来一个例子：

可以很明显的看出，橙色的路径和 (93) 远比绿色的路径和 (0) 大。但是如果选择橙色的路径，初始健康点数至少需要 13，而选择绿色的路径，初始健康点数只需要 8

结合框架分析

回顾一下动态规划的框架：明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义

前三个要素，其实是很好确定的！这个题目的难点在于：定义 dp 数组/函数的含义

下面的所有分析均基于「递归」自顶向下的解法，所以我们需要定义dp()函数

第一种定义方式

定义：dp(i, j)表示dungeon[0..i][0..j]所需的最低初始健康点数，即从左上角 (dungeon[0][0]) 走到dungeon[i][j]所需的最低初始健康点数

所以，现在原问题为：dp(m, n)

我们希望dp(i, j)能够通过dp(i - 1, j)和dp(i, j - 1)推导出来，这样就能不断逼近 base case，也就能够正确进行状态转移

具体来说，「到达A的最小生命值」应该能够由「到 B的最小生命值」和「到达C的最小生命值」推导出来：

但问题是，能推出来么？实际上是不能的

因为按照dp函数的定义，你只知道「能够从左上角到达C的最小生命值」，但并不知道「到达C时的生命值」。

「到达C时的生命值」是进行状态转移的必要参考，举个例子就明白了，假设下图这种情况：

显然，橙色的路径是最优路径。但是根据我们的dp()定义，dp(2, 1) = dp(1, 2) = 1，那我们就无法在d(2, 2)做出正确的决策！

所以说，我们之前对dp数组的定义是错误的，信息量不足，算法无法做出正确的状态转移

第二种定义方式

定义：dp(i, j)表示dungeon[i..m-1][j..n-1]所需的最低初始健康点数，即从dungeon[i][j]走到终点 (右下角) 所需的最低初始健康点数

所以，现在原问题为：dp(0, 0)

此时，我们的 base case 为i = m -1 and j = n -1时，代码如下：

x
public int calculateMinimumHP(int[][] dungeon) {
    // 我们想计算左上角到右下角所需的最小生命值
    return dp(dungeon, 0, 0);
}
private int dp(int[][] dungeon, int i, int) {
    int m = dp.length;
    int n = dp[0].length;
    // base case
    if (i == m - 1 && j == n - 1) {
        return dungeon[i][j] >= 0 ? 1 : -dungeon[i][j] + 1;
    }
    // ...
}

根据新的dp函数定义和 base case，我们想求dp(0, 0)，那就应该试图通过dp(i, j + 1)和dp(i + 1, j)推导出dp(i, j)，这样才能不断逼近 base case，正确进行状态转移

具体来说，「从A到达右下角的最少生命值」应该由「从B到达右下角的最少生命值」和「从C到达右下角的最少生命值」推导出来：

能不能推导出来呢？这次是可以的，假设dp(0, 1) = 5, dp(1, 0) = 4，那么可以肯定要从A走向B，因为 4 小于 5 嘛

那么怎么推出dp(0, 0)是多少呢？

假设A的值为 1，既然知道下一步要往B走，且dp(1, 0) = 4意味着走到dungeon[1][0]的时候至少要有 4 点生命值，那么就可以确定骑士出现在A点时需要 4 - 1 = 3 点初始生命值

那如果A的值为 10，落地就能捡到一个大血瓶，超出了后续需求，4 - 10 = -6 意味着骑士的初始生命值为负数，这显然不可以，骑士的生命值小于 1 就挂了，所以这种情况下骑士的初始生命值应该是 1

综上，状态转移方程已经推出来了：

xxxxxxxxxx
int res = min(
    dp(i + 1, j),
    dp(i, j + 1)
) - dungeon[i][j];

dp(i, j) = res <= 0 ? 1 : res;

代码实现

根据上面的核心逻辑，加一个备忘录消除重叠子问题，就可以直接写出最终的代码了：

xxxxxxxxxx
// 备忘录
private int[][] emeo;
public int calculateMinimumHP(int[][] dungeon) {
    int m = dungeon.length;
    int n = dungeon[0].length;
    emeo = new int[m][n];
    // 由于 emeo 可能存在 0 值，所以需要初始化为 -1
    for (int i = 0; i < m; i++) Arrays.fill(emeo[i], -1);
    return dp(dungeon, 0, 0);
}
private int dp(int[][] dungeon, int i, int j) {
    int m = dungeon.length;
    int n = dungeon[0].length;

    // 越界
    if (i >= m || j >= n) return Integer.MAX_VALUE;

    // base case
    if (i == m - 1 && j == n - 1) {
        return dungeon[i][j] >= 0 ? 1 : -dungeon[i][j] + 1;
    }
    
    // 备忘录中存在
    if (emeo[i][j] != -1) return emeo[i][j];

    // 状态转移
    int res = Math.min(
        dp(dungeon, i + 1, j),
        dp(dungeon, i, j + 1)
    ) - dungeon[i][j];

    emeo[i][j] = res <= 0 ? 1 : res;

    return emeo[i][j];
}

下面再给出一种「递推」自底向上的解法：

x
public int calculateMinimumHP(int[][] dungeon) {
    int m = dungeon.length;
    int n = dungeon[0].length;
    int[][] dp = new int[m][n];

    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            // base case
            if (i == m - 1 && j == n -1) {
                dp[i][j] = dungeon[i][j] >= 0 ? 1 : -dungeon[i][j] + 1;
                continue;
            }
            int min = Integer.MAX_VALUE;
            if (i + 1 < m) min = Math.min(min, dp[i + 1][j]);
            if (j + 1 < n) min = Math.min(min, dp[i][j + 1]);
            int res = min - dungeon[i][j];
            dp[i][j] = res <= 0 ? 1 : res;
        }
    }
    return dp[0][0];
}