174. Dungeon Game (Hard)

1.問題

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

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