[leetcode]174. Dungeon Game

siberiawolf 发布于2019-08-14 16:52 / 1393人阅读

摘要：为了保证骑士可以最终到达，我们可以从终点逆向走到起点。为正数表示是药水，骑士可以相应降低初始血量。为负数表明要增加血量来保证存活。用二维空间来表示当前位置所需的最小血量，不断向左上方走直到起点。用来表示当前层与下一层。

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms
laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0"s) or contain magic orbs that increase the knight"s health (positive integers).

In order to reach the princess as quickly as possible, the knight
decides to move only rightward or downward in each step.

本题为最小路径。在搜索的时候，保持最小值至少为1。
为了保证骑士可以最终到达，我们可以从终点逆向走到起点。每到一个地方有两种选择，向上或者向左。
选择需要初始血量最小的走法。matrix为正数表示是药水，骑士可以相应降低初始血量。为负数表明要增加血量来保证存活。
用二维空间来表示当前位置所需的最小血量，不断向左上方走直到起点。因为一个点只有两种走法，血量只与右边和下边有关。
我们可以减少空间到O(2n)。用来表示当前层与下一层。但是我们是逆向走，在dp[j+1]是已经是当前层，而dp[j]还停留在下一层未更新。所以我们只需一个O(n)空间就行了。

time: O(n^2), space: O(n)

public class Solution {
    public int calculateMinimumHP(int[][] matrix) {
        if(matrix == null || matrix.length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;
        int[] dp = new int[n+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[n-1] = 1;
        for(int i=m-1;i>=0;i--) {
            for(int j=n-1;j>=0;j--){
                dp[j] = Math.max(1 , Math.min(dp[j],dp[j+1]) - matrix[i][j]);
            }   // dp[j] means go down,  dp[j+1] means go right
        }
        return dp[0];
    }
}

time: O(n^2), space: O(n^2)

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
     
        //init dp table
        int[][] h = new int[m][n];
     
        h[m - 1][n - 1] = Math.max(1 - dungeon[m - 1][n - 1], 1);
     
        //init last col
        for (int i = m - 2; i >= 0; i--) {
                h[i][n - 1] = Math.max(h[i + 1][n - 1] - dungeon[i][n - 1], 1);
        }
     
        //init last row
        for (int j = n - 2; j >= 0; j--) {
                h[m - 1][j] = Math.max(h[m - 1][j + 1] - dungeon[m - 1][j], 1);
        }
     
        //calculate dp table
        for (int i = m - 2; i >= 0; i--) {
                for (int j = n - 2; j >= 0; j--) {
                        int down = Math.max(h[i + 1][j] - dungeon[i][j], 1);
                        int right = Math.max(h[i][j + 1] - dungeon[i][j], 1);
                        h[i][j] = Math.min(right, down);
                }
        }
     
        return h[0][0];
    }

私有云混合云 Dungeon Leetcod LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66287.html

174. Dungeon Game

摘要：题目解答这一题最重要的是把所剩血量初始化血量走这一步消耗的血量这句话读懂。那么我们假设是走完后所剩余的血量肯定是大于等于的。如果想存活下来，最少需要上一步血量，即上一步血量然后分类讨论上一步血量的可能性，注意边界情况的初始化即可。题目： The demons had captured the princess (P) and imprisoned her in the bottom-...

wanglu1209 2019-08-14 14:06 评论0 收藏0
[Leetcode] Dungeon Game 地牢游戏

摘要：动态规划复杂度时间空间递归栈思路骑士向右或者向下走，如果血量小于就死掉了，这会使得计算变得很复杂。假设表示点和的血量，表示走到和要扣除的血量。最右下角那个节点没有待逆推的节点，所以我们假设其逆推节点的血量为。 Dungeon Game The demons had captured the princess (P) and imprisoned her in the bottom-r...

taoszu 2019-08-14 12:45 评论0 收藏0
[Leetcode] Nim Game 尼姆游戏

摘要：脑筋急转弯复杂度时间空间思路这题往小说可以追溯到小学奥数或者脑筋急转弯的书中，往大说可以深究到博弈论。代码如果一开始就是的倍数，你就输了，因为对方可以用同样的策略 Nim Game You are playing the following Nim Game with your friend: There is a heap of stones on the table, each ...

cartoon 2019-08-14 12:45 评论0 收藏0
LeetCode[45] Jump Game II

摘要：复杂度思路每次设置一个窗口，观察在这一步下能到达的最远距离，不断的移动这个窗口。计数，需要移动几次，才能覆盖到末尾的值。 LeetCode[45] Jump Game II Given an array of non-negative integers, you are initially positioned at the first index of the array. Eac...

keelii 2019-08-14 15:02 评论0 收藏0
Leetcode PHP题解--D37 682. Baseball Game

摘要：题目链接题目分析给定一个字符串数组，每一个字符串有以下形式数字。直接计算得分。。代表上一轮分数无效。思路这题没什么好说的了。用区分各种情况，进行相应处理即可。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 682. Baseball Game 题目链接 682. Baseball Game 题目分析给定一个字符串数组，每一个字符串有以下形式：数字。直接计算得分。 +。代表本轮...

wzyplus 2019-07-01 12:42 评论0 收藏0