My O(n) space DP Solution with Java


  • 0
    W
    class Solution {
        public int calculateMinimumHP(int[][] dungeon) {
            if (dungeon == null || dungeon.length == 0 || dungeon[0].length == 0) {
                return -1; // input error
            }
            int m = dungeon.length; // number of rows
            int n = dungeon[0].length; // number of columns
            int[] dp = new int[n]; // dp[i]: minimum initial health points
            for (int r = m - 1; r >= 0; r--) { // go from right bottom to left top
                for (int c = n - 1; c >= 0; c--) {
                    if (r == m - 1 && c == n - 1) { // initialize right bottom node
                        dp[c] = Math.max(-dungeon[r][c] + 1, 1);
                        continue;
                    }
                    int right = (c < n - 1) ? dp[c + 1] : Integer.MAX_VALUE;
                    int bottom = (r < m - 1) ? dp[c] : Integer.MAX_VALUE;
                    dp[c] = Math.max(1, Math.min(right, bottom) - dungeon[r][c]);
                }
            }
            return dp[0];
        }
    }
    

Log in to reply
 

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