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

hi 普通 2023年12月20日下午11:24

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        //状态表示f[i][j]为[i,j]到终点所需的最小健康点数
        int n = dungeon.size(), m = dungeon[0].size();
        vector<vector<int>> f(n, vector<int> (m, 1e8));
        f[n - 1][m - 1] = 1 - dungeon[n - 1][m - 1];
        f[n - 1][m - 1] = max(f[n - 1][m - 1], 1); //注意这里是max
        //当最后一个数为正数，前一步会算出一个负数，但健康点数是不能小于1 的

        for(int i = n - 1; i >= 0; i--)
            for(int j = m - 1; j >= 0; j--){
                if(i == n - 1 && j == m - 1) continue; //f[n - 1][m - 1]已经算过了，跳过
        //需要特别考虑一下i+1/j+1 不在二维数组内，f[i][j + 1]或f[i + 1][j]没有值的情况
                if(j < m - 1) f[i][j] = min(f[i][j], f[i][j + 1] - dungeon[i][j]);
                if(i < n - 1) f[i][j] = min(f[i][j], f[i + 1][j] - dungeon[i][j]);

                f[i][j] = max(f[i][j], 1);
        //上一步算的f[i][j]可能为负，证明你最小的点数也能走到最后，而最小生命点数是有要求的，不能小于1
            }

        return f[0][0];
    }
};

0 赞同 0 条回复

June 普通 2023年11月20日上午11:28

“男追女”的错误解法

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
         int n = dungeon.length;
         int m  = dungeon[0].length;
         int[][] dp = new int[n+1][m+1];
         int[][] nowHealth = new int[n+1][m+1]; // 到这一步的累计健康值
         dp[0][0] = 1 - dungeon[0][0] < 0 ? 1 : 1 - dungeon[0][0];
         nowHealth[0][0] = dp[0][0] + dungeon[0][0];

         for(int j=1;j<m;j++)
         {
              if(dungeon[0][j] <= 0)
              {
                  if(nowHealth[0][j-1] + dungeon[0][j] >= 1)
                  {
                      nowHealth[0][j] = nowHealth[0][j-1] + dungeon[0][j];
                      dp[0][j] = dp[0][j-1];
                  }
                  else
                  {
                      dp[0][j] = dp[0][j-1] - (nowHealth[0][j-1] + dungeon[0][j]) + 1;
                      nowHealth[0][j] = 1;
                  }
              }
              else
              {
                  nowHealth[0][j] = nowHealth[0][j-1] + dungeon[0][j];
                  dp[0][j] = dp[0][j-1];
              }
         }

         for(int i=1;i<n;i++)
         {
              if(dungeon[i][0] <= 0)
              {
                  if(nowHealth[i-1][0] + dungeon[i][0] >= 1)
                  {
                      nowHealth[i][0] = nowHealth[i-1][0] + dungeon[i][0];
                      dp[i][0] = dp[i-1][0];
                  }
                  else
                  {
                      dp[i][0] = dp[i-1][0] - (nowHealth[i-1][0] + dungeon[i][0]) + 1;
                      nowHealth[i][0] = 1;
                  }
              }
              else
              {
                  nowHealth[i][0] = nowHealth[i-1][0] + dungeon[i][0];
                  dp[i][0] = dp[i-1][0];
              }
         }
         if(n == 1 || m == 1)
            return dp[n-1][m-1];

        for(int i=1;i<n;i++)
        {
            for(int j=1;j<m;j++)
            {
                int uphealth,updp, righthealth,rightdp;
                if(dungeon[i][j] <= 0)
                {

                    if(nowHealth[i-1][j] + dungeon[i][j] >= 1)
                    {
                        uphealth = nowHealth[i-1][j] + dungeon[i][j];
                        updp = dp[i-1][j];
                    }
                    else
                    {
                        updp = dp[i-1][j] - (nowHealth[i-1][j] + dungeon[i][j]) + 1;
                        uphealth = 1;
                    }


                    if(nowHealth[i][j-1] + dungeon[i][j] >= 1)
                    {
                        righthealth = nowHealth[i][j-1] + dungeon[i][j];
                        rightdp = dp[i][j-1];
                    }
                    else
                    {
                        rightdp = dp[i][j-1] - (nowHealth[i][j-1] + dungeon[i][j]) + 1;
                        righthealth = 1;
                    }
                }
                else
                {
                    righthealth = nowHealth[i][j-1] + dungeon[i][j];
                    rightdp = dp[i][j-1];

                    uphealth = nowHealth[i-1][j] + dungeon[i][j];
                    updp = dp[i-1][j];
                }

                if(updp < rightdp)
                {
                    dp[i][j] = updp;
                    nowHealth[i][j] = uphealth;
                }
                if(updp > rightdp)
                {
                    dp[i][j] = rightdp;
                    nowHealth[i][j] = righthealth;
                }
                else if(uphealth > righthealth)
                {   
                    dp[i][j] = updp;
                    nowHealth[i][j] = uphealth;
                }
                else
                {
                    dp[i][j] = rightdp;
                    nowHealth[i][j] = righthealth;                  
                }
            }
        }

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
                System.out.print(dp[i][j]+" ");
            System.out.println();
        }
        System.out.println();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
                System.out.print(nowHealth[i][j]+" ");
            System.out.println();
        }
        return dp[n-1][m-1];
    }
}

“女追男”的正确解法

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int n = dungeon.length;
        int 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年9月15日下午4:02

//倒着做，确实不好想
class Solution {
    public int[] dx = {-1,0};
    public int[] dy = {0,-1};
    public int calculateMinimumHP(int[][] dungeon) {
        int n = dungeon.length;
        int 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 条回复

Marshan 普通 2023年9月8日下午9:33

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        // 要倒着做确实没想到
        vector<vector<int>> dp(m,vector<int>(n,0));

        dp[m-1][n-1] = max(1 - dungeon[m-1][n-1],1);

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

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

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

0 赞同 0 条回复

Mby 普通 2023年8月22日下午1:03

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        if(dungeon == null || dungeon.length == 0 || dungeon[0].length == 0){
            return 0;
        }
        int rowSize = dungeon.length;
        int colSize = dungeon[0].length;
        int[][] dp = new int[rowSize][colSize];
        //设置最后一个值
        dp[rowSize - 1][colSize - 1] = Math.max(0, -dungeon[rowSize- 1][colSize-1]);

        //设置最后一列的值
        for(int i=rowSize - 2; i >= 0; --i){
            int needMin = dp[i+1][colSize-1] - dungeon[i][colSize-1];
            dp[i][colSize-1] = Math.max(0, needMin);
        }
        //设置最后一行的值
        for(int i = colSize - 2; i >= 0; --i){
            int needMin = dp[rowSize - 1][i + 1] - dungeon[rowSize-1][i];
            dp[rowSize - 1][i] = Math.max(0, needMin);
        }

        for(int i = rowSize - 2; i >= 0; --i){
            for(int j = colSize - 2; j >= 0; --j){
                  //从右边和下边选择一个最小值，然后减去当前的dungeon值
            int needMin = Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j];
            dp[i][j] = Math.max(0, needMin);
            } 
        }
            return dp[0][0] + 1;
    }
}

0 赞同 0 条回复

长河呼叫黄江普通 2023年8月9日下午11:26

8.9 周三
Day30：下面是代码

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        if(dungeon == null || dungeon.length == 0 || dungeon[0].length == 0) return 0;
        int rowSize = dungeon.length;
        int colSize = dungeon[0].length;
        int dp[][] = new int[rowSize][colSize];
        dp[rowSize - 1][colSize -1] = Math.max(0, -dungeon[rowSize - 1][colSize - 1]);
        //最后一列的值
        for(int i = rowSize - 2; i >= 0; i--){
            int needMin = dp[i + 1][colSize - 1] - dungeon[i][colSize - 1];
            dp[i][colSize - 1] = Math.max(0, needMin);
        }
        //最后一行的值
        for(int i = colSize - 2; i >= 0; i--){
            int needMin = dp[rowSize - 1][i + 1] - dungeon[rowSize - 1][i];
            dp[rowSize - 1][i] = Math.max(0,needMin);
        }
        for(int i = rowSize - 2; i >= 0; i--){
            for(int j = colSize - 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;

    }
}

0 赞同 0 条回复

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

共以下 6 个回答

# 回答此问题取消回复

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

共以下 6 个回答

# 回答此问题 取消回复

# 回答此问题取消回复