[LeetCode] Dungeon Game

An interesting problem. The code is also short and clear.

The basic idea is to use a 2d array dp[i][j] to denote the minimum hp that is required before entering dungeon[i][j]. Since the knight needs to be alive after entering the bottom-right cell of the dungeon, we will update dp from bottom-right to top-left. The updating formula is also simple:

dp[i][j] = max(1, min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j]).

Taking the maximum with 1 guarantees that the hp of the knight never drops to or below 0. Since the knight only moves in two directions: rightwards or downwards, each cell (dp[i][j]) is only related to its right (d[i][j + 1]) and down (dp[i + 1][j]) neighbors.

The following code barely translates the above idea, while adding dummy rows and columns for initializations.

 1 class Solution {
 2 public:
 3     int calculateMinimumHP(vector<vector<int>>& dungeon) {
 4         int m = dungeon.size(), n = dungeon[0].size();
 5         vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
 6         dp[m][n - 1] = dp[m - 1][n] = 1; // initialization
 7         for (int i = m - 1; i >= 0; i--)
 8             for (int j = n - 1; j >= 0; j--)
 9                 dp[i][j] = max(min(dp[i][j + 1], dp[i + 1][j]) -dungeon[i][j], 1);
10         return dp[0][0];
11     }
12 };

Of course, the 2d array can be simplified to a 1d array if we've been clear of how dp is updated (in the above code, dp is updated row by row from the bottom one to the top one and in each row it is updated from right to left). The 1d version is as follows.

 1 class Solution {
 2 public:
 3     int calculateMinimumHP(vector<vector<int>>& dungeon) {
 4         int m = dungeon.size(), n = dungeon[0].size();
 5         vector<int> dp(n + 1, INT_MAX); dp[n - 1] = 1; // initialization
 6         for (int i = m - 1; i >= 0; i--)
 7             for (int j = n - 1; j >= 0; j--)
 8                 dp[j] = max(min(dp[j], dp[j + 1]) - dungeon[i][j], 1);
 9         return dp[0];
10     }
11 };

Well, if you get confused, try to run the 2d code on the example in the problem statement and record the values of dp near the corresponding values of dungeon using different colors, as the following picture. After that, you will be clear, even of the 1d code :-)