LeetCode 第174题：地下城游戏

题目描述

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

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

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

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

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

难度

困难

题目链接

点击在LeetCode中查看题目

示例

示例1：

输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出：7
解释：
如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。

示例2：

输入：dungeon = [[0]]
输出：1

提示

• m == dungeon.length
• n == dungeon[i].length
• 1 <= m, n <= 200
• -1000 <= dungeon[i][j] <= 1000

解题思路

方法一：动态规划（从终点到起点）

这道题乍一看可能想从起点到终点做动态规划，但那样会遇到困难，因为我们不知道到达每个位置时需要的最小健康点数。更合适的做法是从终点反向推到起点。

关键点：

1. 定义dp[i][j]为从位置(i,j)到达终点所需的最小初始健康点数
2. 初始条件：dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])，即骑士到达终点的房间后健康值至少为1
3. 状态转移方程：dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
4. 最终答案：dp[0][0]

时间复杂度：O(mn)，其中m和n分别是地下城的行数和列数 空间复杂度：O(mn)

方法二：优化空间的动态规划

可以优化方法一的空间复杂度，只使用一维数组。

关键点：

1. 只使用一个长度为n的一维数组dp
2. 从最后一行开始，逐行向上更新dp数组
3. 对于每一行，从右向左更新dp[j]

时间复杂度：O(m*n) 空间复杂度：O(n)

代码实现

C# 实现

public class Solution {
    public int CalculateMinimumHP(int[][] dungeon) {
        int m = dungeon.Length;
        int n = dungeon[0].Length;
        
        // dp[i][j] 表示从位置(i,j)到达终点所需的最小初始健康点数
        int[,] dp = new int[m, n];
        
        // 初始化终点值
        dp[m-1, n-1] = Math.Max(1, 1 - dungeon[m-1][n-1]);
        
        // 初始化最后一列
        for (int i = m - 2; i >= 0; i--) {
            dp[i, n-1] = Math.Max(1, dp[i+1, n-1] - dungeon[i][n-1]);
        }
        
        // 初始化最后一行
        for (int j = n - 2; j >= 0; j--) {
            dp[m-1, j] = Math.Max(1, dp[m-1, j+1] - dungeon[m-1][j]);
        }
        
        // 计算其他位置的dp值
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                int minHealthNeeded = Math.Min(dp[i+1, j], dp[i, j+1]);
                dp[i, j] = Math.Max(1, minHealthNeeded - dungeon[i][j]);
            }
        }
        
        return dp[0, 0];
    }
}

Python 实现

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        
        # dp[i][j] 表示从位置(i,j)到达终点所需的最小初始健康点数
        dp = [[0] * n for _ in range(m)]
        
        # 初始化终点值
        dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])
        
        # 初始化最后一列
        for i in range(m-2, -1, -1):
            dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1])
            
        # 初始化最后一行
        for j in range(n-2, -1, -1):
            dp[m-1][j] = max(1, dp[m-1][j+1] - dungeon[m-1][j])
            
        # 计算其他位置的dp值
        for i in range(m-2, -1, -1):
            for j in range(n-2, -1, -1):
                min_health_needed = min(dp[i+1][j], dp[i][j+1])
                dp[i][j] = max(1, min_health_needed - dungeon[i][j])
                
        return dp[0][0]

C++ 实现

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        
        // dp[i][j] 表示从位置(i,j)到达终点所需的最小初始健康点数
        vector<vector<int>> dp(m, vector<int>(n, 0));
        
        // 初始化终点值
        dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1]);
        
        // 初始化最后一列
        for (int i = m - 2; i >= 0; i--) {
            dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1]);
        }
        
        // 初始化最后一行
        for (int j = n - 2; j >= 0; j--) {
            dp[m-1][j] = max(1, dp[m-1][j+1] - dungeon[m-1][j]);
        }
        
        // 计算其他位置的dp值
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                int minHealthNeeded = min(dp[i+1][j], dp[i][j+1]);
                dp[i][j] = max(1, minHealthNeeded - dungeon[i][j]);
            }
        }
        
        return dp[0][0];
    }
};

优化空间的实现（C++）

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        
        // dp[j] 表示当前行位置j到达终点所需的最小初始健康点数
        vector<int> dp(n, 0);
        
        // 初始化终点值
        dp[n-1] = max(1, 1 - dungeon[m-1][n-1]);
        
        // 初始化最后一行
        for (int j = n - 2; j >= 0; j--) {
            dp[j] = max(1, dp[j+1] - dungeon[m-1][j]);
        }
        
        // 计算其他行的dp值
        for (int i = m - 2; i >= 0; i--) {
            dp[n-1] = max(1, dp[n-1] - dungeon[i][n-1]);
            
            for (int j = n - 2; j >= 0; j--) {
                int minHealthNeeded = min(dp[j+1], dp[j]);
                dp[j] = max(1, minHealthNeeded - dungeon[i][j]);
            }
        }
        
        return dp[0];
    }
};

性能分析

各语言实现的性能对比：

实现语言	执行用时	内存消耗	特点
C#	100 ms	39.5 MB	实现清晰，性能适中
Python	76 ms	17.3 MB	代码最简洁
C++	4 ms	8.8 MB	性能最优
C++（空间优化）	0 ms	8.7 MB	空间和时间效率均最优

补充说明

代码亮点

1. 反向动态规划的思想，从终点反推到起点
2. 优化空间复杂度的实现，只使用O(n)的额外空间
3. 边界条件的处理，确保健康点数至少为1

常见错误

1. 尝试从起点到终点进行动态规划，难以确定到达每个位置所需的最小健康点数
2. 没有正确处理骑士的健康点数必须始终大于0的约束
3. 没有考虑到负数健康值的情况，如房间值为-10，骑士需要至少11点健康值才能通过

相关题目

• 64. 最小路径和
• 62. 不同路径
• 63. 不同路径 II