Leetcode - Dungeon Game

My code:

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int row = dungeon.length;
        int col = dungeon[0].length;
        dungeon[row - 1][col - 1] = Math.max(1 - dungeon[row - 1][col - 1], 1);
        for (int i = col - 2; i >= 0; i--) {
            dungeon[row - 1][i] = Math.max(dungeon[row - 1][i + 1] - dungeon[row - 1][i], 1);
        }
        for (int i = row - 2; i >= 0; i--) {
            dungeon[i][col - 1] = Math.max(dungeon[i + 1][col - 1] - dungeon[i][col - 1], 1);
        }
        
        for (int i = row - 2; i >= 0; i--) {
            for (int j = col - 2; j >= 0; j--) {
                int down = Math.max(dungeon[i + 1][j] - dungeon[i][j], 1);
                int right = Math.max(dungeon[i][j + 1] - dungeon[i][j], 1);
                dungeon[i][j] = Math.min(down, right);
            }
        }
        
        return dungeon[0][0];
    }
}

reference:
http://www.programcreek.com/2014/03/leetcode-dungeon-game-java/

从右下往左上扫描。

dp[i][j] 表示进入 (i, j) 这个房间之前应该拥有的最小血量，使得王子可以存活。

Anyway, Good luck, Richardo! -- 09/29/2016