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

共以下 1 个回答

• 塔底的仰望 永久会员 2023年9月16日 下午6:59

  dp[i][j]的定义为在第(i,j)格最小初始值

  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 min = Math.min(dp[i + 1][j], dp[i][j + 1]);
                  dp[i][j] = Math.max(min - dungeon[i][j], 1);
              }
          }
          return dp[0][0];
      }
  }
  

  0 赞同 0 条回复

  登录以回复