174 Dungeon Game

题目类似于DP经典问题里面的数字三角形。技巧是简单的从后向前搜索。

Java

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 --)
                dungeon[i][j] = Math.max(Math.min(dungeon[i + 1][j], dungeon[i][j + 1]) - dungeon[i][j], 1);
        return dungeon[0][0];
    }
}