Hard

题目描述

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

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

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

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

返回确保骑士能够拯救到公主所需的最低初始健康点数。

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

示例 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

解题思路

这道题目需要用动态规划来解决，关键在于从终点（右下角）逆向思考。

核心思路： 我们需要确保骑士在任何时刻的血量都大于0。如果从起点正向思考会很复杂，因为我们不知道后面需要多少血量。但如果从终点反向思考，问题就变得清晰了：我们需要计算到达每个位置时所需的最小血量。

状态定义： dp[i][j] 表示从位置 (i,j) 到达公主位置所需的最小血量。

状态转移：

  • 对于右下角位置：dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])
  • 对于其他位置：dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])

这里的逻辑是：

  1. 进入当前房间后，血量变为：当前血量 + dungeon[i][j]
  2. 要保证进入后能到达终点，需要：当前血量 + dungeon[i][j] >= dp[下一个位置]
  3. 因此：当前血量 >= dp[下一个位置] - dungeon[i][j]
  4. 同时血量必须至少为1：当前血量 >= 1

优化：可以直接在原数组上修改，或使用滚动数组优化空间复杂度。

代码实现

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        
        // 从右下角开始，逆向计算
        dp[m-1][n-1] = max(1, 1 - dungeon[m-1][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]);
        }
        
        // 填充最后一列
        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 i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                int minNext = min(dp[i+1][j], dp[i][j+1]);
                dp[i][j] = max(1, minNext - dungeon[i][j]);
            }
        }
        
        return dp[0][0];
    }
};

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        dp = [[0] * n for _ in range(m)]
        
        # 从右下角开始，逆向计算
        dp[m-1][n-1] = max(1, 1 - dungeon[m-1][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])
        
        # 填充最后一列
        for i in range(m-2, -1, -1):
            dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1])
        
        # 填充其余位置
        for i in range(m-2, -1, -1):
            for j in range(n-2, -1, -1):
                min_next = min(dp[i+1][j], dp[i][j+1])
                dp[i][j] = max(1, min_next - dungeon[i][j])
        
        return dp[0][0]

public class Solution {
    public int CalculateMinimumHP(int[][] dungeon) {
        int m = dungeon.Length, n = dungeon[0].Length;
        int[,] dp = new int[m, n];
        
        // 从右下角开始，逆向计算
        dp[m-1, n-1] = Math.Max(1, 1 - dungeon[m-1][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]);
        }
        
        // 填充最后一列
        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 i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                int minNext = Math.Min(dp[i+1, j], dp[i, j+1]);
                dp[i, j] = Math.Max(1, minNext - dungeon[i][j]);
            }
        }
        
        return dp[0, 0];
    }
}

var calculateMinimumHP = function(dungeon) {
    const m = dungeon.length, n = dungeon[0].length;
    const dp = Array(m).fill().map(() => Array(n).fill(0));
    
    // 从右下角开始，逆向计算
    dp[m-1][n-1] = Math.max(1, 1 - dungeon[m-1][n-1]);
    
    // 填充最后一行
    for (let j = n - 2; j >= 0; j--) {
        dp[m-1][j] = Math.max(1, dp[m-1][j+1] - dungeon[m-1][j]);
    }
    
    // 填充最后一列
    for (let i = m - 2; i >= 0; i--) {
        dp[i][n-1] = Math.max(1, dp[i+1][n-1] - dungeon[i][n-1]);
    }
    
    // 填充其余位置
    for (let i = m - 2; i >= 0; i--) {
        for (let j = n - 2; j >= 0; j--) {
            const minNext = Math.min(dp[i+1][j], dp[i][j+1]);
            dp[i][j] = Math.max(1, minNext - dungeon[i][j]);
        }
    }
    
    return dp[0][0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(m × n)
空间复杂度O(m × n)

其中 m 和 n 分别是地下城的行数和列数。空间复杂度可以优化到 O(n)，使用滚动数组或直接在原数组上修改。

相关题目