Dynamic solution c++


  • 0
    Z
    class Solution {
    public:
    	int calculateMinimumHP(vector<vector<int>>& dungeon) {
    		if (dungeon.empty())
    			return 0;
    		int n = dungeon.size();
    		int m = dungeon[0].size();
    
    		vector<int> dp(m, 0);
    
    		//start from bottom line ,right to left
    		for (int j = m - 1; j >= 0; j--) {
    			if (j == m - 1)
    				dp[m - 1] = dungeon[n-1][m - 1] > 0 ? 1 : 1 - dungeon[n-1][m - 1];//bottom right initial
    			else {
    				dp[j] = dp[j+1] - dungeon[n - 1][j] > 0 ? dp[j+1] - dungeon[n - 1][j] : 1;//initialbottom line
    			}
    		}
    		for (int i = n - 2; i >= 0;i--) {//from bottom second line to update
    			for (int j = m - 1; j >= 0; j--) {
    				if (j == m - 1) {
    					dp[j] = dp[j] - dungeon[i][j]>0 ? dp[j] - dungeon[i][j] : 1;//when j = m-1, use only dp[j] to update
    				}
    				else {
    					dp[j] = min(dp[j], dp[j + 1]) - dungeon[i][j] > 0 ? min(dp[j], dp[j + 1]) - dungeon[i][j] : 1;//use minimum of dp[j] and dp[j+1]to update
    				}
    			}
    		}
    
    		return dp[0];
    	}
    };
    
    

Log in to reply
 

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