> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/174.-dungeon-game-hard.md).

# 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)