174 Dungeon Game

這一題直接參考其他人的概念，看到以下的程式碼。

class Solution {
public:
    int calculateMinimumHP(vector<vector<int> > &dungeon) {
        int M = dungeon.size();
        int N = dungeon[0].size();
        // hp[i][j] represents the min hp needed at position (i, j)
        // Add dummy row and column at bottom and right side
        vector<vector<int> > hp(M + 1, vector<int>(N + 1, INT_MAX));
        hp[M][N - 1] = 1;
        hp[M - 1][N] = 1;
        for (int i = M - 1; i >= 0; i--) {
            for (int j = N - 1; j >= 0; j--) {
                int need = min(hp[i + 1][j], hp[i][j + 1]) - dungeon[i][j];
                hp[i][j] = need <= 0 ? 1 : need;
            }
        }
        return hp[0][0];
    }
};

看完應該會有幾個疑惑，把這幾個疑惑看清楚就會懂這段code了。

問題

1. 為什麼計算need是取min(hp[i + 1][j], hp[i][j + 1])?
2. 為什麼計算need是要-dungeon[i][j]?
3. 為什麼 need <= 0 時，要把hp[i][j]設成1?

答案

1. 因為我們想要找出用min hp就能到終點的路，所以往右或往下的兩格中，比較小的那格就是我們想要走的路。
2. 舉例來說，因為hp[i][j]跟hp[i][j+1]只差在hp[i][j]多吃到dungeon[i][j]，而hp[i][j]就是想要算吃到dungeon[i][j]之前需要到多少的HP，所以自然是要-dungeon[i][j]。
3. 因為need<=0表示走到這格的時候，可以吃到+HP的東西，所以need<=0。但因為minHP是1，故只要求走到這格的時候，HP有1即可。