Dungeon Game(Hard) 地牢游戏

Leetcode Source

解题思路：动态规划

dp[i][j]表示进入这个格子后保证knight不会死所需要的最小HP。如果一个格子的值为负，那么进入这个格子之前knight需要有的最小HP是-dungeon[i][j] + 1.如果格子的值非负，那么最小HP需求就是1.

这里可以看出DP的方向是从最右下角开始一直到左上角。首先dp[m-1][n-1] = Math.max(1, -dungeon[m-1][n-1] + 1).

递归方程是dp[i][j] = Math.max(1, Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]).

public int calculateMinimumHP(int[][] dungeon) {
    if(dungeon.length == 0)
        return 0;
    int m = dungeon.length, n = dungeon[0].length;

    int[][] dp = new int[m][n];
    dp[m - 1][n - 1] = dungeon[m - 1][n - 1] >= 0 ? 1 : -dungeon[m - 1][n - 1] + 1;
    for(int i = m - 2; i >= 0; i--){
        dp[i][n - 1] = Math.max(dp[i + 1][n - 1] - dungeon[i][n - 1], 1);
    }
    for(int j = n - 2; j >= 0; j--){
        dp[m - 1][j] = Math.max(dp[m - 1][j + 1] - dungeon[m - 1][j], 1);
    }

    for(int i = m - 2; i >= 0; i--){
        for(int j = n - 2; j >= 0; j--){
            dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
        }
    }
    return dp[0][0];
}