java dp solution O(n) space O(mn) time

  • 0

    dp array is holding the minimum damage the knight would suffer if starting from this room to reach the princess. Calculation has to be done from princess to knight instead of the other way around. And if the damage at specific room is higher than that of future, the value at this dp cell should be updated to the damage in this room.

    Note that the damage I mentioned in this solution is negative, so the minimum damage is calculated by Math.max();

    public int calculateMinimumHP(int[][] dungeon) {
            if(dungeon.length == 0 || dungeon[0].length == 0) return 0;
            int m = dungeon.length;
            int n = dungeon[0].length;
            int i = m-1;
            int[] dp = new int[n];
            dp[n-1] = dungeon[i][n-1];
            for(int j = n-2; j >= 0; j--) {
                dp[j] = Math.min(dp[j+1] + dungeon[i][j], dungeon[i][j]);
            while(i >= 0) {
                int[] last = dp;
                dp = new int[n];
                dp[n-1] = Math.min(last[n-1] + dungeon[i][n-1], dungeon[i][n-1]);
                for(int j = n-2; j >= 0; j--) {
                    dp[j] = Math.min(Math.max(last[j], dp[j+1]) + dungeon[i][j], dungeon[i][j]);
            return Math.max(1-dp[0], 1);

Log in to reply

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