Java dp


  • 0
    J
        public int calculateMinimumHP(int[][] dungeon) {
            int m = dungeon.length, n = dungeon[0].length;
            int[][] dp = new int[m][n];
            if (dungeon[m - 1][n - 1] >= 0) dp[m - 1][n - 1] = 1;
            else dp[m - 1][n - 1] = 1 - dungeon[m - 1][n - 1];
            for (int i = m - 1; i >= 0; i--) {
                for (int j = n - 1; j >= 0; j--) {
                    if (j == n - 1 && i == m - 1) continue;
                    int curMin = Integer.MAX_VALUE;
                    if (j < n - 1) curMin = Math.min(curMin, dp[i][j + 1]);
                    if (i < m - 1) curMin = Math.min(curMin, dp[i + 1][j]);
                    dp[i][j] = curMin - dungeon[i][j];
                    if (dp[i][j] <= 0) dp[i][j] = 1;
                }
            }
            return dp[0][0];
        }
    

Log in to reply
 

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