JAVA short DP + explaination


  • 1
    S
    public class Solution {
        public int calculateMinimumHP(int[][] dungeon) {
            int column = dungeon.length;
            int row = dungeon[0].length;
            int[][] dp = new int[column][row];
            dp[column-1][row-1] = Math.max(1-dungeon[column-1][row-1], 1);
            
            for(int i=column-2; i>=0; i--) {
                dp[i][row-1] = Math.max(1, dp[i+1][row-1]-dungeon[i][row-1]);
            }
            for(int j=row-2; j>=0; j--) {
                dp[column-1][j] = Math.max(1, dp[column-1][j+1]-dungeon[column-1][j]); 
            }
            for(int i=column-2; i>=0; i--) {
                for(int j=row-2; j>=0; j--) {
                    dp[i][j] = Math.max(1, Math.min(dp[i+1][j]-dungeon[i][j], dp[i][j+1]-dungeon[i][j]));
                }
            }
            return dp[0][0];
        }
    }

  • 1
    S

    short explain:

    dp from bottom-right to top-left

    we create the matrix dp[i][j] represent the "LEAST HEALTH" for knight when enter into the dungeon[i][j]

    then we got the equtation:

    dp[i][j] >= 1 AND ( dp[i][j] - dungeon[i][j] >= dp[i+1][j] OR dp[i][j] - dungeon[i][j] >= dp[i][j+1] )

    initial the bottom and right most line, start iteration, got result in dp[0][0]


  • 0
    J

    Nice Solution


Log in to reply
 

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