# 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
```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 -> 才會是答案
*/
```
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/174.-dungeon-game.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.