【动态规划专题】LeetCode 174. 地下城游戏-跟着帅地玩副业，开拓第二曲线PlayOffer

王位詮釋普通 2024年4月14日下午5:27

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        if(dungeon==null||dungeon.length<=0||dungeon[0].length<=0){
            return 0;
        }
        int m = dungeon.length;
        int n = dungeon[0].length;
        //dp[i][j]表示从i,j位置到终点所需要的最少血量
        int[][] dp = new int[m][n];
        //初始值
        //如果dungeon[m-1][m-1]是正值，说明这里会加血，所以初始值不需要设置
        //如果是负值的话，说明这里会减血，所以需要设置初始值
        dp[m-1][n-1] = Math.max(-dungeon[m-1][n-1],0);
        //设置最后一行的值
        for(int i = n-2;i>=0;i--){
            int needMin = dp[m-1][i+1]-dungeon[m-1][i];
            dp[m-1][i] = Math.max(needMin,0);
        }
        //设置最后一列的值
        for(int i=m-2;i>=0;i--){
            int needMin = dp[i+1][n-1]-dungeon[i][n-1];
            dp[i][n-1] = Math.max(needMin,0);
        }

        for(int i=m-2;i>=0;i--){
            for(int j = n-2;j>=0;j--){
                int needMin = Math.min(dp[i][j+1],dp[i+1][j])-dungeon[i][j];
                dp[i][j] = Math.max(0,needMin);
            }
        }
        return dp[0][0]+1;
    }
}
思路：由于这个题在往后便利过程中会涉及到加血，
所以i,j位置的值可能是和后面的值有关系，不像之前的题那样，
i，j位置的值只与左或者上的值有关，所以这个题可以从后往前推，
如果从后往前推，之前的动归思想都是从开始位置到当前位置的xxx，
而这里的dp[i][j]表示的就是从当前位置到最后所需要的血量。
这时候前一位置的血量要根据右边和下边的值来判断，
所需要的最小血量needMin = Math.min(dp[i+1][j],dp[i][j+1]),
dp[i][j] = Math.max(needMin-dungeon[i][j],0)

0 赞同 0 条回复

云无深雁影普通 2024年4月11日上午12:40

class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int[][] dp = new int[dungeon.length][dungeon[0].length];
dp[dungeon.length-1][dungeon[0].length-1] = 1 + Math.max(0, – dungeon[dungeon.length-1][dungeon[0].length-1]);
for(int i = dungeon.length – 2; i >= 0; i–){
dp[i][dungeon[0].length – 1] = Math.max(1,dp[i + 1][dungeon[0].length – 1] – dungeon[i][dungeon[0].length – 1]);
}
for(int j = dungeon[0].length – 2; j >= 0; j–){
dp[dungeon.length – 1][j] = Math.max(1, dp[dungeon.length – 1][j + 1] – dungeon[dungeon.length – 1][j]);
}

    for(int i = dungeon.length - 2; i >= 0; i--){
        for(int j = dungeon[0].length - 2; j >= 0; j--){
            dp[i][j] = Math.max(1,Math.min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j]);
        }
    }
    return dp[0][0];
}

}
//dp
//空间复杂度On2
//时间复杂度On2

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年4月8日下午10:07

找了一个能看懂的题解，用的是递归方法，通过memory数组减少重复计算

class Solution{
private int rowSize = 0;
private int colSize = 0;
private int[][] globalDun = null;
public int calculateMinimumHP(int[][] dungeon) {
    if (dungeon == null || dungeon.length == 0 || dungeon[0].length == 0) {
        return 0;
    }
    rowSize = dungeon.length;
    colSize = dungeon[0].length;
    globalDun = dungeon;
    int[][] memory = new int[rowSize][colSize];
    // 初始化为-1，便于区别是否计算过结果了 否则超时
    for (int i = 0; i < rowSize; ++i) {
        for (int j = 0; j < colSize; ++j) {
            memory[i][j] = -1;
        }
    }
    return dfs(0, 0, memory) + 1;
}

public int dfs (int rowIndex, int colIndex,  int[][] memory) {
    if (rowIndex >= rowSize || colIndex  >=  colSize) {
        return Integer.MAX_VALUE;
    }
    // 不为-1就是计算过了，直接返回结果。
    if (memory[rowIndex][colIndex] != -1) {
        return memory[rowIndex][colIndex];
    }
    if (rowIndex == rowSize - 1 && colIndex == colSize - 1) {
        if (globalDun[rowIndex][colIndex] >= 0) {
            return 0;
        } else {
            return -globalDun[rowIndex][colIndex];
        }
    }
    int right = dfs(rowIndex, colIndex + 1, memory);
    int down = dfs(rowIndex + 1, colIndex, memory);
    int needMin = Math.min(right, down) - globalDun[rowIndex][colIndex];
    int res = 0;
    if (needMin < 0) {
        res =  0;
    } else {
        res =  needMin;
    }
    memory[rowIndex][colIndex] = res;
    System.out.println(rowIndex+ " "+colIndex + " "  + res);
    return res;
}
}

0 赞同 0 条回复

紫芝普通 2024年4月3日下午11:41

思路：使用动态规划的思想反向递推

“`c++
class Solution {
public:
int calculateMinimumHP(vector>& dungeon) {
int m = dungeon.size(), n = dungeon[0].size();
vector> dp(m, vector(n, 0));
dp[m-1][n-1] = dungeon[m-1][n-1];
// 设置最后一列 i
int i=m-2, j=n-1;
for (; i>=0; i–) {
if (dp[i+1][j] < 0) { dp[i][j] = dp[i+1][j] + dungeon[i][j]; } else { dp[i][j] = dungeon[i][j]; } } // 设置最后一行 j i=m-1, j=n-2; for (; j>=0; j–) {
if (dp[i][j+1] < 0) { dp[i][j] = dp[i][j+1] + dungeon[i][j]; } else { dp[i][j] = dungeon[i][j]; } } for (int i=m-2; i>=0; i–) {
for (int j=n-2; j>=0; j–) {
int maxi = max(dp[i+1][j], dp[i][j+1]);
if (maxi < 0) { dp[i][j] = maxi + dungeon[i][j]; } else { dp[i][j] = dungeon[i][j]; } } } if (dp[0][0] >= 0) return 1;
return 1 – dp[0][0];
}
};

优化为一维数组
```c++
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<int> dp(n, 0);
        dp[n-1] = dungeon[m-1][n-1];
        // 设置最后一行 j
        int i=m-1, j=n-2;
        for (; j>=0; j--) {
            if (dp[j+1] < 0) {
                dp[j] = dp[j+1] + dungeon[i][j];
            } else {
                dp[j] = dungeon[i][j];
            }
        }
        for (int i=m-2; i>=0; i--) {
            if (dp[n-1] < 0) {
                dp[n-1] = dp[n-1] + dungeon[i][n-1];
            } else {
                dp[n-1] = dungeon[i][n-1];
            }
            for (int j=n-2; j>=0; j--) {
                int maxi = max(dp[j], dp[j+1]);
                if (maxi < 0) {
                    dp[j] = maxi + dungeon[i][j];
                } else {
                    dp[j] = dungeon[i][j];
                }
            }
        }
        if (dp[0] >= 0) return 1;
        return 1 - dp[0];
    }
};

0 赞同 0 条回复

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

共以下 4 个回答

# 回答此问题取消回复

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

共以下 4 个回答

# 回答此问题 取消回复

# 回答此问题取消回复