0%

leetcode每日一题-地下城游戏

Posted on In ,

地下城游戏

image1

动态规划提，如果从$(0,0)$开始正向思考转移方程，那么既要考虑路径和，又要考虑最低血量，无法用动态规划解决。需要注意在每一格的最低血量都为1，低于1，那么骑士就会死亡。我们可以从反向思考，假设dp[i][j]表示在[i][j]位置上扣完血后剩余的最少血量，那么dp[m-1][n-1]=1，即骑士最后仅剩下一滴血。因为骑士有两种走法，向右和向下，那么dp[i][j]的转移方程为：
$$
dp[i][j] = min(right, down)\
right = max(dp[i][j+1]-dungeon[i][j+1], 1)\
down = max(dp[i+1][j]-dungeon[i+1][j], 1)\
$$
这里$right$和$down$分别代表在[i][j]处向右走和向下走的最低血量。

边界条件类似转移方程。

1
class Solution {
2
    public int calculateMinimumHP(int[][] dungeon) {
3
        int m = dungeon.length;
4
        int n = dungeon[0].length;
5
        int[][] dp = new int[m][n];
6
        //dp[i][j]表示在[i][j]位置上扣完血之后剩余的最少血量
7
        dp[m-1][n-1] = 1;
8
        for(int i=m-2; i>=0; i--){
9
            dp[i][n-1] = Math.max(dp[i+1][n-1]-dungeon[i+1][n-1], 1);
10
        }
11
        for(int j=n-2; j>=0; j--){
12
            dp[m-1][j] = Math.max(dp[m-1][j+1]-dungeon[m-1][j+1], 1);
13
        }
14
        for(int i=m-2; i>=0; i--){
15
            for(int j=n-2; j>=0; j--){
16
                //向右
17
                int right = Math.max(dp[i][j+1]-dungeon[i][j+1],1);
18
                //向下
19
                int down = Math.max(dp[i+1][j]-dungeon[i+1][j],1);
20
                dp[i][j] = Math.min(right,down); 
21
            }
22
        }
23
        //起始处的最低血量等于在起始位置扣完血后的最低血量减去要扣的血量
24
        return Math.max(dp[0][0]-dungeon[0][0],1);
25
    }
26
}

复杂度分析：

  • 时间复杂度：$O(mn)$。
  • 空间复杂度：$O(mn)$。