My java DP solution O(nm) with space O(n)


  • 2
    J

    DP from bottom to top and right to left.

    public class Solution {
        public int calculateMinimumHP(int[][] dungeon) {
        	int w = dungeon[0].length;
        	int[] dp = new int[w + 1];
        	for(int x = 0; x<dp.length; x++)
        		if(x != w-1)
        			dp[x] = Integer.MAX_VALUE;
        	
        	for(int y=dungeon.length-1; y>=0; y--)
        		for(int x=w-1; x>=0; x--)
        			dp[x] = Math.max(0, Math.min(dp[x+1], dp[x]) - dungeon[y][x]);
    
            return dp[0] + 1;
        }
    }

  • 0
    S

    Excellent dp solution with sliding array! thanks!


Log in to reply
 

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