Dungeon Game

题目描述

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.

解题方法

这道题目有两种解法

Binary search + 验证

从0到sys.maxint，不断地取中间值，然后验证时候能够存活，不能的话二分舍去一半再找。

利用的Binary search的思想，但是时间复杂度很高

DP

这种max, min的问题我们要想到可以用DP做，但是难点是在于如果定下dp代表的状态和连接function。

因为这道题跟unique path不同的地方在于这里要求每一步都不能小于0。从走的顺序推的问题在于不能确定下一步是否会为0， 而反过来推的话就可以去掉这一个烦恼，因为只要再满足现在的位置，后面的肯定可以存活，所以我们从终点往前推。

state

dp[i][j]代表从(i,j)位置走到终点所需要的最小起始生命值

function

那么

dp[i][j] = max(  min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j], 0 )

如果这个比较难读的话，起始应该是

dp[i][j] = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]
if dp[i][j] < 0:
    dp[i][j] = 0

当前dungeon[i][j]如果是正的表示加血，dp[i][j]的起始生命值就应该减去，反之也是。 因为起始生命值不能为负数，从前面走到这一步也不可以是负的，所以小于0的数都应该改为0

init

初始值就是两个边的值

result

dp[0][0] + 1

Solution

class Solution(object):
    def calculateMinimumHP(self, dungeon):
        """
        :type dungeon: List[List[int]]
        :rtype: int
        """
        if not dungeon:
            return -1
        row = len(dungeon)
        col = len(dungeon[0])

        #dp[i][j] means from i,j to row-1, col-1
        dp = [[0 for i in range(col)] for j in range(row)]
        dp[row-1][col-1] = max(0 - dungeon[row-1][col-1], 0)

        #init states
        for i in range(row-2, -1, -1):
            dp[i][col-1] = max(dp[i+1][col-1] - dungeon[i][col-1], 0)

        for j in range(col-2, -1, -1):
            dp[row-1][j] = max(dp[row-1][j+1] - dungeon[row-1][j], 0)

        for i in range(row-2, -1, -1):
            for j in range(col-2, -1, -1):
                dp[i][j] = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]
                if dp[i][j] < 0:
                    dp[i][j] = 0
        return dp[0][0] + 1

Reference

• dp
• 二分法