【LeetCode】*0174 地下城游戏

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

# -*- coding:utf-8 -*-

"""
      ┏┛ ┻━━━━━┛ ┻┓
      ┃　　　　　　 ┃
      ┃　　　━　　　┃
      ┃　┳┛　  ┗┳　┃
      ┃　　　　　　 ┃
      ┃　　　┻　　　┃
      ┃　　　　　　 ┃
      ┗━┓　　　┏━━━┛
        ┃　　　┃   神兽保佑
        ┃　　　┃   代码无BUG！
        ┃　　　┗━━━━━━━━━┓
        ┃　　　　　　　    ┣┓
        ┃　　　　         ┏┛
        ┗━┓ ┓ ┏━━━┳ ┓ ┏━┛
          ┃ ┫ ┫   ┃ ┫ ┫
          ┗━┻━┛   ┗━┻━┛
"""


class Solution(object):
    def calculateMinimumHP(self, dungeon):
        """
        :type dungeon: List[List[int]]
        :rtype: int
        """
        n = len(dungeon)
        m = len(dungeon[0])
        dp = [[float('inf') for _ in range(m + 1)] for _ in range(n + 1)]
        dp[n][m - 1] = dp[n - 1][m] = 1
        for i in range(n - 1, -1, -1):
            for j in range(m - 1, -1, -1):
                dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])
        return dp[0][0]
        pass


if __name__ == '__main__':
    map = [
        [-2, -3, 3],
        [-5, -10, 1],
        [10, 30, -5]
    ]
    print(Solution().calculateMinimumHP(map))
    pass

思路：这道题第一眼看到就是dp，但是这道题。。它dp的不一样。

这道题需要使用反向dp，原因就是对于当前的最优状态，由于下一位置取决于当前位置的剩余血量，举个例子，A路径到这里剩余血量为5，而B路径剩余血量为0，同时B路径比A路径更优（对于当前结点来说），而对于下一个结点，A很可能依据当前剩余血量优势反超B的效果，因此正向dp变得不可行。

因此使用反向dp，从结果向开始dp。