↓Skip to main content

【LeetCode 174】地下城游戏

·51 words·1 min
WFUing
Author
WFUing
A graduate who loves coding.
Table of Contents

  • 链接：https://leetcode.cn/problems/dungeon-game/description/

难点
#

本题的难点在于怎么处理血量增加的问题, 增加血量不能为之前的损失提供帮助，只会对后续有帮助。这意味着从王子救公主的思路想dp是困难的，但是公主救王子的思路dp很好做，从后往前推，当前如果可以治愈，那么当前的最小初始血量就是已经扣除的血量减去治疗量，注意不可以<1。 这意味着过量治疗。

代码
# 

class Solution {

    public int calculateMinimumHP(int[][] dungeon) {
        int l1 = dungeon.length;
        int l2 = dungeon[0].length;
        int[][] dp = new int[l1+1][l2+1];
        for(int i=0;i<=l1;i++){
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[l1][l2-1]=1;
        dp[l1-1][l2]=1;
        for(int i=l1-1;i>=0;i--){
            for(int j=l2-1;j>=0;j--){
                dp[i][j]=Math.max(Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j], 1);
            }
        }
        return dp[0][0];
    }

}