LeetCode 174. 地下城游戏

Categories:

题目描述
思路分析
1. 解法一：逆向动态规划（推荐）
相似题目

题目描述

✅ 174. 地下城游戏

思路分析

解法一：逆向动态规划（推荐）

核心思路：

正向 DP 难以同时维护”当前血量”和”最低血量”两个状态，因此采用逆向思路

定义 dp[i][j] 为从 (i, j) 出发到达终点所需的最低初始血量

终点状态：dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])

转移方程：骑士从 (i,j) 可向右或向下移动，取两个方向所需血量的较小值减去当前格子的值，且至少为 1

dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])

最终答案为 dp[0][0]，即从起点出发所需的最低初始血量

复杂度分析：

时间复杂度：O(m × n)，其中 m、n 分别为地牢的行数和列数

空间复杂度：O(m × n)，可优化为 O(n) 滚动数组

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 + 1][n + 1];

        // 边界初始化为极大值，防止越界取最小值时误选边界
        for (int i = 0; i <= m; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }

        // 终点右侧和下侧的虚拟格子设为 1，便于转移
        dp[m][n - 1] = 1;
        dp[m - 1][n] = 1;

        // 从右下角逆推到左上角
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; 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];
    }
}

func calculateMinimumHP(dungeon [][]int) int {
    m, n := len(dungeon), len(dungeon[0])

    // dp[i][j] 表示从 (i,j) 到终点所需最低初始血量
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
        for j := range dp[i] {
            dp[i][j] = math.MaxInt32
        }
    }

    // 终点右侧和下侧的虚拟格子设为 1
    dp[m][n-1] = 1
    dp[m-1][n] = 1

    // 从右下角逆推到左上角
    for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 0; j-- {
            minNext := min(dp[i+1][j], dp[i][j+1])
            dp[i][j] = max(1, minNext-dungeon[i][j])
        }
    }

    return dp[0][0]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

相似题目

题目	难度	考察点
64. 最小路径和	中等	动态规划、矩阵
62. 不同路径	中等	动态规划
63. 不同路径 II	中等	动态规划
741. 摘樱桃	困难	动态规划、矩阵
1289. 下降路径最小和 II	困难	动态规划
931. 下降路径最小和	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/97652987