174. Dungeon Game

因為要求的是 在 0,0 的初始生命最少要多少
所以 如果dp[i][j] 狀態是由 dp[i+1][j], dp[i][j+1] 決定的話, 變成要從 m-1, n-1 推過來

跟一般 robot 走到右下角, 是相反的方式, 因為那種是 dp[i][j] 狀態是由 dp[i-1][j], dp[i][j-1]
一路推到 m-1, n-1, 才會知道總共的走法


T: O(mn)
S: O(mn)

```java
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m][n];

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i == m-1 && j == n-1) {
                    dp[i][j] = 1 - dungeon[i][j]; // so in m-1, n-1, needs health 6 (dp[2][2]) to live (6 - 5 == 1)
                } else if (i == m-1) {
                    dp[i][j] = dp[i][j+1] - dungeon[i][j]; // dp[2][1] = dp[2][2] - dungeon[2][1] = 6 - 30 = -24 -> but at least 1! so dp[2][1] = 1
                } else if (j == n-1) {                     // so dp[2][0] also = 1
                    dp[i][j] = dp[i+1][j] - dungeon[i][j];
                } else {
                    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); // 如果是補藥, dp 會變負的, 代表後來會吃到補藥, 變成負的血, 但這樣的初始血量是不合理的, 最小是 1
                // System.out.println("dp["+i + "][" + j + "]=" + dp[i][j]);
            }
        }
        

        return dp[0][0];
    }
}
/**
dp[2][2]=6
dp[2][1]=1
dp[2][0]=1
dp[1][2]=5
dp[1][1]=11
dp[1][0]=6
dp[0][2]=2
dp[0][1]=5
dp[0][0]=7

dp:
7 5 2
6 11 5
1 1  6

in 0,0
dp[i][j] = Math.min(dp[i+1][j] - dungeon[i][j], dp[i][j+1] - dungeon[i][j]);
dp[0][0] = Math.min(6 -(-2),  5 -(-2)) = Math.min(8, 7) = 7
 */

/*

T: O(mn)
S: O(mn)

dp[i][j]: is the health value(at least 1) which is alive for arriving m-1, n-1 ( so in m-1, n-1 it's 6)

一路弟推到0,0
(開始的初始值, so in m-1, n-1 終點（base case）, it's 1 - dungeon[m-1][n-1], 因為都吃完藥水或扣完生命, 我們要讓他活著, 就是 1)

dp[i][j] = Math.min(dp[i+1][j] - dungeon[i][j], dp[i][j+1] - dungeon[i][j]);
for each dp, dp[i][j] = Math.max(dp[i][j], 1); can't let health < 1


跟一般 dp 走到右下角的狀態不一樣

一般的是 dp[i][j] = min(dp[i-1][j], dp[i][j-1])

這題是反過來的
dp[i][j] = min(dp[i+1][j], dp[i][j+1])
因為能不能繼續走下去取決於 是不是有足夠的血在一開始
所以 這一開始的血 要看 min(dp[i+1][j], dp[i][j+1])
選一個比較小的來走(可能是扣血的), 這樣一開始的血量可以給予少一點

所以變成從右下角開始算, 算到 (0,0), 就知道一開始需要多少血

但還要注意, 因為要算一開始血量, 所以要減掉  dungeon[i][j] or dungeon[i][j] 

dp[i][j] = Math.min(dp[i+1][j] - dungeon[i][j], dp[i][j+1] - dungeon[i][j]);
ex: 

(0,0) - (-3) -> 代表從 0,0 過來至少要 3滴血才能到 (0,1)

但這題不能 < 0 , 過程中
so dp[i][j] = Math.max(dp[i][j], 1);

最後 dp[0][0] 還要算扣掉自己的（或加血）
dp[0][0] = dp[0][0] - dungeon[0][0];
dp[0][0] = Math.max(dp[0][0], 1);
ex: dungeon[0][0] = -2

所以 dp[0][0] + 2 -> 才會是答案
*/
```