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

共以下 5 个回答

• 宁 永久会员 2023年3月19日 下午8:54

  class Solution {
      public int calculateMinimumHP(int[][] dungeon) {
          //dp i j 表示能到达某个位置的最大值
          //难点在于前面的选择会影响后面的结果，因此反过来思考 从右下到左上。
          //血量 + d >= 下一个位置的最低血量 血量 >=下一个位置min（只要有能走通的就行） - d
          int m = dungeon.length;
          int n = dungeon[0].length;
          int[][] dp = new int[m + 1][n + 1];
          for(int i = 0; i <= m; i++){
              Arrays.fill(dp[i], Integer.MAX_VALUE);
          }
          dp[m][n - 1] = dp[m - 1][n] = 1;
          for(int i = m - 1; i >= 0; i--){
              for(int j = n - 1; j >= 0; j--){
                  int min = Math.min(dp[i][j + 1], dp[i + 1][j]);
                  dp[i][j] = Math.max(1, min - dungeon[i][j]);
              }
          }
          return dp[0][0];
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• lucca 普通 2023年1月20日 上午12:20

  逆向DP

  • 时间复杂度 O(NM)
  • 空间复杂度 O(NM)
  • 从右下到左上遍历，每个点的决策为：
    • 决定向左还是向右（取两点初值的最小值）
    • 考虑当前点的初值，用取到的最小值减去当前点给的血包（或者耗得血量）
    • 如果会加血，可以少设置点初值
    • 如果是耗血，要多设初值

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

  0 赞同 0 条回复

  登录以回复
• 訁訁訁訁訁 普通 2022年12月1日 下午12:53

  时间空间复杂度O(MN)

  /**
  每次都和1判断的原因是，骑士需要维持的最小血量为1
  拿dp[i][j+1]-dungeon[i][j]举例，如果小于1，说明dungeon是正数，是加血的地方，则只需要维持血量为1即可
  如果大于1说明dungeon是负数，是扣血的地方，扣完血得到下方和右方的最小值即可，能得到最少需要的生命值
   */
  class Solution {
      public int calculateMinimumHP(int[][] dungeon) {
          //既然最小，则保证终点时骑士的血量最少
          int m = dungeon.length;
          int n = dungeon[0].length;
          //dp表示在i，j位置骑士需要的最小生命值
          int[][] dp = new int[m][n];
          dp[m-1][n-1] = dungeon[m-1][n-1] > 0 ? 1 : 1-dungeon[m-1][n-1];
          for(int i = m-1;i >= 0;i--) {
              for(int j = n-1;j >= 0;j--) {
                  if(i == m - 1 && j == n - 1) continue;
                  //最后一行
                  if(i == m - 1) dp[i][j] = Math.max(1, dp[i][j + 1] - dungeon[i][j]);
                  //最后一列
                  else if(j == n-1) dp[i][j] =Math.max(1, dp[i+1][j] - dungeon[i][j]);
                  else 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 条回复

  登录以回复
• 西西弗斯的石头 永久会员 2022年11月29日 下午11:43

  时间空间复杂度为O（mn）

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

  0 赞同 0 条回复

  登录以回复
• Mooby 普通 2022年11月29日 下午10:27

  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];
      }
  }
  

  时间：O(mn)，空间：O(mn)

  0 赞同 0 条回复

  登录以回复