LeetCode 174. 地下城游戏

￡神魔★判官ぃ 2022-10-25 04:46 125阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]

//解法一：二分+正向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];
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/2da541aa401d4a44aabba4ac879e1115.png