LeetCode 174. 地下城游戏-蒲公英云

LeetCode 174. 地下城游戏

在这里插入图片描述

//解法一：二分+正向dp
//https://leetcode-cn.com/problems/dungeon-game/solution/er-fen-cwo-te-yao-sou-bao-by-tian-xin-yue-yuan-3/
class Solution {
    private boolean search(int[][] d, int hp){
        int m = d.length;
        int n = d[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 0; i <= m; i++)
            Arrays.fill(dp[i], -0x3f3f3f3f);//边界条件，从1开始，第一行上面和第一列左边都是负无穷
        dp[0][1] = dp[1][0] = hp;//边界条件，hp
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                int val = Math.max(dp[i - 1][j], dp[i][j - 1]) + d[i - 1][j - 1];
                if(val <= 0)//没血了，别走了
                    continue;
                dp[i][j] = val;
            }
        }
        return dp[m][n] > 0;//还有血吗
    }
    public int calculateMinimumHP(int[][] dungeon) {
        int l = 0;
        int r = 0x3f3f3f3f;
        int mid;
        while(l < r){
            mid = l + r >> 1;
            if(search(dungeon, mid)){
                r = mid;
            }else
                l = mid + 1;
        }
        return Math.max(l, 1);
    }
}
//解法二：逆向dp  因为
//https://leetcode-cn.com/problems/dungeon-game/solution/di-xia-cheng-you-xi-by-leetcode-solution/
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int n = dungeon.length, m = dungeon[0].length;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; ++i) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[n][m - 1] = dp[n - 1][m] = 1;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = m - 1; j >= 0; --j) {
                int minn = Math.min(dp[i + 1][j], dp[i][j + 1]);
                dp[i][j] = Math.max(minn - dungeon[i][j], 1);
            }
        }
        return dp[0][0];
    }
}