LeetCode刷题实战174：地下城游戏-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 地下城游戏 ，我们先来看题面：

https://leetcode-cn.com/problems/dungeon-game/

Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

题意

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

解题

https://blog.csdn.net/qq_17550379/article/details/86243097

一看到这个问题首先想到的就是动态规划，其次想的就是自顶向下，但是这样想的话就会有一个问题，就是我们需要判断每次到达一个房间后，我们的血量不能是负数，这给我们编写代码造成了很大的困难。如果采用自底向上的思路去做的话，那么问题就会变得简单很多（而且我觉得你应该做到，拿到这个问题首先想到的就是自底向上，这是一种直觉）。我们只需要取右和下的最小值（我们需要计算最少的能量），然后减去dungoen[i][j]，并且保证到达当前房间后的血量大于等于0就行了

f(i,j)=max(0,min(f(i+1,j),f(i,j+1))−dungeon[i][j])

对于边界问题我们单独处理。最后我们只需要取结果f(0,0)+1即可（根据题目中的例子）。Python代码如下：

class Solution:
    def calculateMinimumHP(self, dungeon):
        """
        :type dungeon: List[List[int]]
        :rtype: int
        """
        row, col = len(dungeon), len(dungeon[0])
        mem = [[0]*col for _ in range(row)]

        for i in range(row-1,-1,-1):
            for j in range(col-1,-1,-1):
                if i == row-1 and j == col-1:
                    mem[i][j] = max(0, -dungeon[i][j])
                elif i == row-1:
                    mem[i][j] = max(0, mem[i][j+1] - dungeon[i][j])
                elif j == col-1:
                    mem[i][j] = max(0, mem[i+1][j] - dungeon[i][j])
                else:
                    mem[i][j] = max(0, min(mem[i+1][j], mem[i][j+1]) - dungeon[i][j])
                
        return mem[0][0] + 1