# 174. Dungeon Game (Hard)

## 1.問題

* 找出最快到右下角的方格的途徑, 並使總和為1的話, 請問原點的值應該要多少?

![](/files/-LIWEDfAf0NyV7Fr1LPV)

## 2.想法

* Dynamic programming
  * DP矩陣存的是要到下一步的成本 (至少要多少)
    * 最右下角的DP值為: 1或是(1 - 最右下角方格值) -> 找最大值
    * 成本的算法為下一個方格的DP值 - 目前方格的值, 如果是負數則設為1
    * 如果走到了最下面一排或最左邊一列, 則不需要考慮往其他方向走的可能
    * 如果是其他地方的DP值為: 往下走DP或是往右走DP的最小值

## 3.程式碼

```
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        if (dungeon.size() == 0 || dungeon[0].size() == 0) {
            return 1;
        }
        int n = dungeon.size();
        int m = dungeon[0].size();
        vector<vector<int>> dp(n, vector<int>(m, 0));
        
        for(int i = n - 1; i >= 0; i--) {
            for(int j = m - 1; j >= 0; j--) {
                if ( i == n - 1 && j == m - 1) {
                    dp[i][j] = max(1, 1 - dungeon[i][j]);
                }
                else if (i == n - 1) {
                    dp[i][j] = max(1, dp[i][j + 1] - dungeon[i][j]);
                }
                else if (j == m - 1) {
                    dp[i][j] = max(1, dp[i + 1][j] - dungeon[i][j]);
                }
                else
                {
                    dp[i][j] = min(max(1, dp[i][j + 1] - dungeon[i][j]), max(1, dp[i + 1][j] - dungeon[i][j]));
                }
            }   
        }
        return dp[0][0];
    }
};
```

## 4.Performance

![](/files/-LIWF3xt2nPGaOE93HF9)


---

# 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://jenhsuan.gitbook.io/algorithm/leetcode/174.-dungeon-game-hard.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.