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

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

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

shuaidi

更新于 3 年前 227 8

共以下 8 个回答

九号球普通 2023年12月9日上午11:16

“`java
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
//从右下角往左上角走，i,j位置需要的最小能量为dp[i][j]，那么i-1，j位置需要的最小能量就是dp[i][j] – dungeon[i][j]，并且因为骑士能量小于1就会死掉，所以dp[i][j]>=1
//公式为dp[i][j] = max(Math.min(dp[i+1][j],dp[i][j+1]) – dungeon[i][j],1),dp[0][0]即为所求
int m = dungeon.length;
int n = dungeon[0].length;
//因为i=m-1或j=n-1时，公式会出现数组越界，所以dp数组范围边界需要是m和n
int[][] dp = new int[m+1][n+1];
for (int i = 0; i <= m; i++) { Arrays.fill(dp[i], Integer.MAX_VALUE); } //i=m-1,j=n-1时，最后剩余的能量大于等于1即可，所以公式后面的值赋值为1即可 dp[m-1][n] = 1; dp[m][n-1] = 1; for (int i = m - 1; i >= 0; i–) {
for (int j = n – 1; j >= 0; j–) {
dp[i][j] = Math.max(Math.min(dp[i+1][j],dp[i][j+1]) – dungeon[i][j], 1);
}
}
return dp[0][0];
}
}

0 赞同 0 条回复

登录以回复

张开怀普通 2023年7月24日下午8:11

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int n = dungeon.size(), m = dungeon[0].size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
        dp[n][m - 1] = dp[n - 1][m] = 1;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = m - 1; j >= 0; --j) {
                int minn = min(dp[i + 1][j], dp[i][j + 1]);
                dp[i][j] = max(minn - dungeon[i][j], 1);
            }
        }
        return dp[0][0];
    }
};

时间复杂度：O(mn)
空间复杂度：O(mn)

0 赞同 0 条回复

Dsjh 普通 2023年7月24日下午5:26

MY

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m=dungeon.size(),n=dungeon[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
        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--){
                dp[i][j] = min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j];
                // 需要的最低血量为负数，那么血量为1
                dp[i][j] = max(dp[i][j],1);
            }
        }
        return dp[0][0];
    }
};

0 赞同 0 条回复

花老爷普通 2023年7月23日下午5:07

动态规划，官解
时间：O(mn)
空间：O(mn)

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int n = dungeon.length, m = dungeon[0].length;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; ++i) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[n][m - 1] = dp[n - 1][m] = 1;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = m - 1; j >= 0; --j) {
                int minn = Math.min(dp[i + 1][j], dp[i][j + 1]);
                dp[i][j] = Math.max(minn - dungeon[i][j], 1);
            }
        }
        return dp[0][0];
    }
}

0 赞同 0 条回复

怀瑾永久会员 2023年7月23日下午3:54

C++实现

“`C++
class Solution {
public:
int calculateMinimumHP(vector>& dungeon) {
int m = dungeon.size(), n = dungeon[0].size();
vector> dp(m+1, vector(n+1,INT_MAX));
for(int i=m-1;i>=0;i–)
{
for(int j=n-1;j>=0;j–)
{
if(i==m-1&&j==n-1)
{
if(dungeon[i][j]<0)
dp[i][j]=-1*dungeon[i][j]+1;
else
dp[i][j]=1;
continue;
}
int minv = min(dp[i+1][j], dp[i][j+1]);
dp[i][j]=max(minv-dungeon[i][j], 1);
}
}
return dp[0][0];
}
};
```

0 赞同 0 条回复

登录以回复

Vow the vow。普通 2023年7月23日下午2:39

真的难

public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length, n = dungeon[0].length;
        int[][] f = new int[m][n];

        f[m-1][n-1] = dungeon[m-1][n-1] > 0 ? 0 : -dungeon[m-1][n-1];
        for(int i = m-2; i >= 0; i--){
            int need = f[i+1][n-1] - dungeon[i][n-1];
            f[i][n-1] = Math.max(0,need);
        }
        for(int j = n-2; j >= 0; j--){
            int need = f[m-1][j+1] - dungeon[m-1][j];
            f[m-1][j] = Math.max(0,need);
        }
        for(int i = m-2; i >= 0; i--){
            for(int j = n-2; j >= 0; j--){
                int need = Math.min(f[i+1][j],f[i][j+1]) - dungeon[i][j];
                f[i][j] = need < 0 ? 0 : need;
                // System.out.println(f[i][j]);
            }
        }
        return f[0][0] + 1;
    }

0 赞同 0 条回复

yxy 普通 2023年7月22日下午8:31

时间复杂度O(mn)

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> dp(m+1, vector<int>(n+1,INT_MAX));
        for(int i=m-1;i>=0;i--)
        {
            for(int j=n-1;j>=0;j--)
            {
                if(i==m-1&&j==n-1)
                {
                    if(dungeon[i][j]<0)
                        dp[i][j]=-1*dungeon[i][j]+1;
                    else
                        dp[i][j]=1;
                    continue;
                }
                int minv = min(dp[i+1][j], dp[i][j+1]);
                dp[i][j]=max(minv-dungeon[i][j], 1);
            }
        }
        return dp[0][0];
    }
};

0 赞同 0 条回复

Yodl. 普通 2023年7月22日下午6:06

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        //状态表示 dp[i][j], 从该位置到终点所需的最小健康点数
        int m = dungeon.size();
        int n = dungeon[0].size();

        //dp表 初始化
        vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
        dp[m][n-1] = 1;

        for(int i= m-1;i>=0;--i)
        {
            for(int j = n-1;j>=0;--j)
            {
                dp[i][j] = min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j];
                if(dp[i][j]<=0)
                dp[i][j] = 1;
            }
        }

        return dp[0][0];
    }
};

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

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

共以下 8 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复