another c++ dp solution


  • 0
    class Solution {
     public:
      int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int x = dungeon.size() - 1, y = dungeon[0].size() - 1;
        vector<int> dp(y + 1, 0);
    
        dp[y] = dungeon[x][y] >= 0 ? 1 : 1 - dungeon[x][y];
    
        for (int i = x; i >= 0; i--)
          for (int j = y; j >= 0; j--) {
            if (i == x && j == y) continue;
            int down = 0x3f3f3f3f;
            if (i < x) {
              if (dungeon[i][j] >= dp[j])
                down = 1;
              else
                down = dp[j] - dungeon[i][j];
            }
    
            int right = 0x3f3f3f3f;
            if (j + 1 <= y) {
              if (dungeon[i][j] >= dp[j + 1])
                right = 1;
              else
                right = dp[j + 1] - dungeon[i][j];
            }
    
            dp[j] = min(down, right);
          }
        return dp[0];
      }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.