Share my c++ DP solution with explanation


  • 8
    K

    ###dp[i][j] means start from point (i,j) end at point (n-1,m-1) need at least dp[i][j] health.###
    dp[i][j] = min( max( dp[i+1][j] - dungeon[i][j], 1),
    max( dp[i][j+1] - dungeon[i][j], 1) );

    class Solution { 
    public:
        int calculateMinimumHP(vector<vector<int> > &dungeon) {
            int n = dungeon.size();
            int m = dungeon[0].size();
            int dp[n][m];
            memset(dp,0,sizeof(dp));
            for(int i=n-1;i>=0;--i){
                for(int j=m-1; j>=0; --j){
                    if(i+1==n && j+1 == m){
                        dp[i][j] = max(1-dungeon[i][j],1);
                        continue;
                    }
                    if(j+1<m){
                        dp[i][j] = max(dp[i][j+1] - dungeon[i][j],1);
                    }
                    if(i+1<n){
                        if(dp[i][j])
                            dp[i][j] = min(dp[i][j],max(dp[i+1][j] - dungeon[i][j],1));
                        else 
                            dp[i][j] = max(dp[i+1][j]-dungeon[i][j],1);
                    }
                }
            }
    
            return dp[0][0];
        }
    };

  • 0
    K

    Came up with basically the same solution. Why is the runtime complexity O(n^2)?

    class Solution {
    public:
        int calculateMinimumHP(vector<vector<int> > &dungeon) {
            int widthMinusOne = dungeon.size()-1;
            int heightMinusOne = dungeon[0].size()-1;
            int j, hpNeededLater, hpNeeded;
            bool bottomFlag, rightEdgeFlag;
            for (int i = widthMinusOne; 0 <= i; i--){
              rightEdgeFlag = i == widthMinusOne ? true : false;
              for (j = heightMinusOne; 0 <= j; j--){
                bottomFlag = j == heightMinusOne ? true : false;
                if (bottomFlag && rightEdgeFlag)
                    hpNeededLater = 0;
                  else if (bottomFlag)
                    hpNeededLater = dungeon[i+1][j];
                  else if (rightEdgeFlag)
                    hpNeededLater = dungeon[i][j+1];
                  else
                    hpNeededLater = min(dungeon[i+1][j], dungeon[i][j+1]);
                  hpNeeded = hpNeededLater - dungeon[i][j];
                  dungeon[i][j] = hpNeeded < 0 ? 0 : hpNeeded;
                }
              }
              return dungeon[0][0]+1;
        }
    };

  • 0
    K

    sorry,it's O(n*m).


Log in to reply
 

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