174. Dungeon Game - cocoder39/coco39_LC GitHub Wiki

174. Dungeon Game

Determine the minimum initial health of the knight should be, not the maximum health the knight can have when arriving bottom-right, tell the difference.

 3 -20 30
-3   4  0

for the latter goal, the way would be right->right->down, however the initial health would be 18 while correct answer is 1.

suppose hps[i][j] is the health points the knight should possess when arriving dungeon[i][j], then supply = min(hps[i + 1][j], hps[i][j + 1]) - dungeon[i][j]. If supply <= 0, then there is no need for extra supply , assign 1 to hps[i][j], otherwise assign supply to hps[i][j]

tips:

vector<vector<int>> hps(m + 1, vector<int>(n + 1, INT_MAX)); 
        hps[m][n - 1] = 1;
        hps[m - 1][n] = 1;

int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        
        vector<vector<int>> hps(m + 1, vector<int>(n + 1, INT_MAX)); //hp[i][j] is the health point at dungeon[i][j]
        hps[m][n - 1] = 1;
        hps[m - 1][n] = 1;
        
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int hp = min(hps[i + 1][j], hps[i][j + 1]) - dungeon[i][j];
                hps[i][j] = hp > 0 ? hp : 1;
            }
        }
        return hps[0][0];
    }

int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        
        vector<vector<int>> hps(2, vector<int>(n + 1, INT_MAX)); //hp[i][j] is the health point at dungeon[i][j]
        hps[1][n - 1] = 1;
        
        int cur = 0, next = 1;
        for (int i = m - 1; i >= 0; i--) {
            hps[cur][n] = i == m - 1 ? 1 : INT_MAX;
            for (int j = n - 1; j >= 0; j--) {
                int hp = min(hps[next][j], hps[cur][j + 1]) - dungeon[i][j];
                hps[cur][j] = hp > 0 ? hp : 1;
            }
            swap(cur, next);
        }
        return hps[next][0];
    }
⚠️ **GitHub.com Fallback** ⚠️