Skip to content

174. Dungeon Game 👍

  • Time: $O(mn)$
  • Space: $O(mn) \to O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  int calculateMinimumHP(vector<vector<int>>& dungeon) {
    const int m = dungeon.size();
    const int 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];
        dp[i][j] = max(dp[i][j], 1);
      }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int calculateMinimumHP(int[][] dungeon) {
    final int m = dungeon.length;
    final int n = dungeon[0].length;
    int[][] dp = new int[m + 1][n + 1];
    Arrays.stream(dp).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
    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] = 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];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def calculateMinimumHP(self, dungeon: list[list[int]]) -> int:
    m = len(dungeon)
    n = len(dungeon[0])
    dp = [math.inf] * (n + 1)
    dp[n - 1] = 1

    for i in reversed(range(m)):
      for j in reversed(range(n)):
        dp[j] = min(dp[j], dp[j + 1]) - dungeon[i][j]
        dp[j] = max(dp[j], 1)

    return dp[0]