题目

LeetCode.174.地下城游戏（困难）

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。

说明:

骑士的健康点数没有上限。
任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

题解

设dungeon[i][j]为地牢的第i行第j列的点数，可正、可负、可零。

这题跟最小路径和不一样的点在于：在任意格子，都要求骑士的生命值x >= 1。

如果骑士位于某行某列，则要求x >= 1 && x + dungeon[i][j] >= 1，不等式两侧的项换个位置也就是：x >= 1 && x >= 1 - dungeon[i][j]，我们要求最低的生命值，可得x = maxOf(1, 1 - dungeon[i][j])。

但是骑士是要在走动的，光看当前位置的点数，是不知道当前生命值够不够用，需要知道后面的路径需要的最少生命值是多少，假设是y，那么当前位置就要满足x >= 1 && x + dungeon[i][j] >= y，我们要求最低的生命值，可得x = maxOf(1, y - dungeon[i][j])。

状态转移的过程就出来了，是要从末尾往开头递推，才能得出结果。

从左上到右下的路径，有两种选择，往右走、往下走。不知道往哪走所需的最低初始健康点数最少，就两个都试一遍，取最小的。

边界条件

在最后一行，只能向右走，无法向下走。
在最后一列，只能向下走，无法向右走。

回溯递归解法

class Solution {
    fun calculateMinimumHP(dungeon: Array<IntArray>): Int {
        val m = dungeon.size
        val n = dungeon[0].size

        fun findMinHp(r: Int, c: Int): Int {
            if (r == m - 1 && c == n - 1) return maxOf(1, 1 - dungeon[r][c])
            return when {
                r == m - 1 -> maxOf(1, findMinHp(r, c + 1) - dungeon[r][c])
                c == n - 1 -> maxOf(1, findMinHp(r + 1, c) - dungeon[r][c])
                else -> maxOf(1, minOf(findMinHp(r, c + 1), findMinHp(r + 1, c)) - dungeon[r][c])
            }
        }
        
        return findMinHp(0, 0)
    }
}

递归存在重叠子问题，例如findMinHp(r + 1, c)会执行多次，需要记录中间状态。

记忆化递归

class Solution {
    fun calculateMinimumHP(dungeon: Array<IntArray>): Int {
        val m = dungeon.size
        val n = dungeon[0].size
        val memo = Array(m) { IntArray(n) { -1 } }

        fun findMinHp(r: Int, c: Int): Int {
            if (memo[r][c] != -1) return memo[r][c]
            val result =  if (r == m - 1 && c == n - 1) maxOf(1, 1 - dungeon[r][c])
            else when {
                r == m - 1 -> maxOf(1, findMinHp(r, c + 1) - dungeon[r][c])
                c == n - 1 -> maxOf(1, findMinHp(r + 1, c) - dungeon[r][c])
                else -> maxOf(1, minOf(findMinHp(r, c + 1), findMinHp(r + 1, c)) - dungeon[r][c])
            }
            memo[r][c] = result
            return result
        }
        
        return findMinHp(0, 0)
    }
}

自底向上的动态规划

记忆化递归已经给出了状态转移方程，需要注意的是要从最右下角开始往左上角递推，才能得到结果。

设dp[i][j]表示骑士位于第i行第j列格子时要达到公主处所需要的最小生命值。

状态转移方程

最右下角：dp[i][j] = maxOf(1, 1 - dungeon[m - 1][n - 1])。
最后一列：dp[i][j] = maxOf(1, dp[r + 1][c] - dungeon[r][c])。
最后一行：dp[i][j] = maxOf(1, dp[r][c + 1] - dungeon[r][c])。
其他行和列：dp[i][j] = maxOf(1, minOf(dp[r][c + 1], dp[r + 1][c]) - dungeon[r][c])。

class Solution {
    fun calculateMinimumHP(dungeon: Array<IntArray>): Int {
        val m = dungeon.size
        val n = dungeon[0].size
        val dp = Array(m) { IntArray(n) { 0 } }

        dp[m - 1][n - 1] = maxOf(1, 1 - dungeon[m - 1][n - 1])

        for (i in m - 2 downTo 0) {
            dp[i][n - 1] = maxOf(1, dp[i + 1][n - 1] - dungeon[i][n - 1])
        }

        for (i in n - 2 downTo 0) {
            dp[m - 1][i] = maxOf(1, dp[m - 1][i + 1] - dungeon[m - 1][i])
        }

        for (r in m - 2 downTo 0) {
            for (c in n - 2 downTo 0) {
                dp[r][c] = maxOf(1, minOf(dp[r][c + 1], dp[r + 1][c]) - dungeon[r][c])
            }
        }

        return dp[0][0]
    }
}