Java solution only using DP[] no need of 2d Dp[][]


  • 0
    O
    public class Solution {
        public int calculateMinimumHP(int[][] dungeon) {
            int[] dp = new int[dungeon[0].length];
            int m = dungeon.length-1;
            int n = dungeon[0].length-1;
            for(int i = m; i >= 0; i--) {
                for(int j = n; j >= 0; j--) {
                    if(i == m) {
                        if(j != n) {
                            dp[j] = Math.max(1, dp[j+1] - dungeon[i][j]);
                        } else {
                            dp[j] = Math.max(1, 1 - dungeon[i][j]);
                        }
                    }
                    if(i < m) {
                        if(j == n) {
                            dp[j] = Math.max(1, dp[j] - dungeon[i][j]); 
                        } else {
                            dp[j] = Math.max(1, Math.min(dp[j+1],dp[j]) - dungeon[i][j]);
                        }
                    }
                }
            }
            return dp[0];
        }
    }
    

Log in to reply
 

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