【动态规划专题】LeetCode 174. 地下城游戏

本问题对应课程链接：剑指offer刷题第七期

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi

更新于 2 年前 161 3

共以下 3 个回答

陆狗陆狗普通 2025年1月2日下午10:25

解题思路
– 颠倒写dp[i][j]，表示i，j到终点的最小初始血量
– dp[i][j]=Math.min(dp[i+1][j],dp[i][j+1])dungeon[i][j]，且必须>=1，表示扣掉dungeon[i][j]之后至少要给我留下1点血
【题解1】

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        // 颠倒写dp[i][j]，表示i，j到终点的最小初始血量
        // dp[i][j]=Math.min(dp[i+1][j],dp[i][j+1])dungeon[i][j]，且必须>=1
        // 初始值 dp[m][n]=1-dungeon[i][j]，最下边和最右边
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m][n];
        // 【错误】扣掉dungeon[m - 1][n - 1]之后至少要给我留下1点血
        dp[m - 1][n - 1] = Math.max(1 - dungeon[m - 1][n - 1], 1);
        // 最后一行
        for (int j = n - 2; j >= 0; j--) {
            dp[m - 1][j] = Math.max(dp[m - 1][j + 1] - dungeon[m - 1][j], 1);
        }
        // 最后一列
        for (int i = m - 2; i >= 0; i--) {
            dp[i][n - 1] = Math.max(dp[i + 1][n - 1] - dungeon[i][n - 1], 1);
        }
        // dp全循环
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                int minValue = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                // 【错误】扣掉dungeon[i][j]之后至少要给我留下1点血
                dp[i][j] = Math.max(minValue, 1);
            }
        }

        return dp[0][0];

    }
}

错误点1：扣掉dungeon[m – 1][n – 1]之后至少要给我留下1点血
错误点2：扣掉dungeon[i][j]之后至少要给我留下1点血

0 赞同 0 条回复

Aatorx 永久会员 2024年12月27日下午3:33

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        int k;
        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[m - 1][n - 1] = max(-dungeon[m - 1][n - 1] + 1, 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 k = min(dp[i + 1][j], dp[i][j + 1]);
                dp[i][j] = max(1, k - dungeon[i][j]);
            }
        }
        return dp[0][0];
    }
};

从终点向起点走，dp数组记录需要的最低血量，若为负数则变为1。
时间复杂度O(Mn)，空间复杂度O(Mn)。

0 赞同 0 条回复

秋山丽奈普通 2024年12月24日下午9:46

思路：从后向前推导

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {

        int row = dungeon.length;
        int col = dungeon[0].length;

        // 最后一个节点 若加血 则无需额外血 
        if (dungeon[row - 1][col - 1] > 0){
            dungeon[row - 1][col - 1] = 0;
        }

        // 初始 右边界 只能从下方到达  
        for (int i = row - 2; i >= 0; i--){
            dungeon[i][col - 1] = dungeon[i][col - 1] + dungeon[i + 1][col - 1];
            if (dungeon[i][col - 1] > 0){
                // 加血 无需额外血 
                dungeon[i][col - 1] = 0;
            }
        }

        // 初始 下边界 只能从右侧到达 
        for (int i = col - 2; i >= 0; i--){
            dungeon[row - 1][i] = dungeon[row - 1][i] + dungeon[row - 1][i + 1];
            if (dungeon[row - 1][i] > 0){
                // 加血 无需额外血 
                dungeon[row - 1][i] = 0;
            }
        }

        // 递推 
        for (int i = row - 2; i >= 0; i--){
            for (int j = col - 2; j >= 0; j--){
                dungeon[i][j] = dungeon[i][j] + Math.max(dungeon[i + 1][j], dungeon[i][j + 1]);
                if (dungeon[i][j] > 0) dungeon[i][j] = 0;
            }
        }

        // 返回起点 
        return dungeon[0][0] = dungeon[0][0] > 0 ? 1 : -dungeon[0][0] + 1;
    }
}

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

【动态规划专题】LeetCode 174. 地下城游戏

共以下 3 个回答

# 回答此问题 取消回复

# 回答此问题取消回复