LeetCode 174 地下城游戏

本题实际编码难度不高，但是更重视对动态规划“无后效性”性质的考察，同时应当注意特定的题目里动态规划的方向会影响答案的数值和有效性。

题目描述

原题链接如下： LeetCode 174 地下城游戏

题目大意

骑士的初始 HP 最少为 1，而且要保证在移动的路径上 HP 也始终不能小于 1（包括起点和终点）。

输入与输出

示例输入为：

骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数对应输出为：

1

7

解题思路

一开始很容易想到使用动态规划的解法，但是如果要使用通常的从 0 下标开始的遍历则会违反动态规划中的“无后效性”原则：已经确定的子问题的解答受到后续子问题内容的严重影响，不能确定不变。对应到本题中的情况就是，后续格子里面对骑士生命值的变动会导致初始路线和生命值大幅改变。举一个简单的特例如下：

这个例子中如果终点为 -3（如上所示），那么理想路线是 右 -> 右 -> 下 -> 下，初始 HP 为 3 即可；但如果终点的值是非负数，则理想路线则是 下 -> 右 -> 右 -> 下，初始 HP 为 2。那么在遍历到下标为 (1, 2) 的单元格的时候就无法确定子问题的答案。

实际本问题应该从结果反推答案，即反向动态规划。令 $dp(i, j)$ 表示从坐标 (i, j) 到终点所需的最小初始值。换句话说，当我们到达坐标 (i, j) 时，如果此时我们的路径和不小于 $dp(i, j)$，我们就能到达终点。在坐标 (i, j) 处我们只能够到达 (i + 1, j) 和 (i, j + 1) 这两处，只要选择其中一个的较小值 min，使 $dp(i, j) \ge min - dugeon(i, j)$ 即可。另外，需要注意初始值不能小于 1，则可以得到递推方程：

$$dp(i, j) = \max {(\min {(dp(i + 1, j), dp(i, j + 1))}, 1)}$$

当然，递推的起点就是地牢的终点它对应的子问题答案是确定的：

$$dp(m-1,n-1) = \max {(1 - dungeon(m-1,n-1),1)}$$

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun calculateMinimumHP(dungeon: Array<IntArray>): Int {
        if (dungeon.isEmpty()) return 1
        val m = dungeon.size
        val n = dungeon[0].size
        val dp = IntArray(n + 1) { Int.MAX_VALUE }
        dp[n - 1] = 1
        for (i in m - 1 downTo 0) {
            for (j in n - 1 downTo 0) {
                dp[j] = minOf(dp[j + 1], dp[j]) - dungeon[i][j]
                dp[j] = maxOf(dp[j], 1)
            }
        }
        return dp[0]
    }
}

注意：本题中的递推公式里面当前项数值只和下方和右方的格子相关，可以使用一维数组优化空间复杂度，不再赘述。