# 174. Dungeon Game (Hard)

## 1.問題

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

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LIW69AMEk6ft0Vwv3Ox%2F-LIWEDfAf0NyV7Fr1LPV%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-07-28%20%E4%B8%8B%E5%8D%8810.11.08.png?alt=media\&token=76a2b019-02fa-4c9b-89a4-f2815f0fdfab)

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

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LIW69AMEk6ft0Vwv3Ox%2F-LIWF3xt2nPGaOE93HF9%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-07-28%20%E4%B8%8B%E5%8D%8810.16.50.png?alt=media\&token=c28f2a8c-d816-44c2-926d-ba9b2d14c64f)