題目鏈接
難度：困難 ??????類型： 動(dòng)態(tài)規(guī)劃

一些惡魔抓住了公主（P）并將她關(guān)在了地下城的右下角。地下城是由 M x N 個(gè)房間組成的二維網(wǎng)格。我們英勇的騎士（K）最初被安置在左上角的房間里，他必須穿過地下城并通過對(duì)抗惡魔來拯救公主。

騎士的初始健康點(diǎn)數(shù)為一個(gè)正整數(shù)。如果他的健康點(diǎn)數(shù)在某一時(shí)刻降至 0 或以下，他會(huì)立即死亡。

有些房間由惡魔守衛(wèi)，因此騎士在進(jìn)入這些房間時(shí)會(huì)失去健康點(diǎn)數(shù)（若房間里的值為負(fù)整數(shù)，則表示騎士將損失健康點(diǎn)數(shù)）；其他房間要么是空的（房間里的值為 0），要么包含增加騎士健康點(diǎn)數(shù)的魔法球（若房間里的值為正整數(shù)，則表示騎士將增加健康點(diǎn)數(shù)）。

為了盡快到達(dá)公主，騎士決定每次只向右或向下移動(dòng)一步。

編寫一個(gè)函數(shù)來計(jì)算確保騎士能夠拯救到公主所需的最低初始健康點(diǎn)數(shù)。

例如，考慮到如下布局的地下城，如果騎士遵循最佳路徑 右 -> 右 -> 下 -> 下，則騎士的初始健康點(diǎn)數(shù)至少為 7。

說明:

騎士的健康點(diǎn)數(shù)沒有上限。

任何房間都可能對(duì)騎士的健康點(diǎn)數(shù)造成威脅，也可能增加騎士的健康點(diǎn)數(shù)，包括騎士進(jìn)入的左上角房間以及公主被監(jiān)禁的右下角房間。

解題思路

為了使初始健康點(diǎn)數(shù)最少，騎士成功救出公主時(shí)的健康值為1，倒推
問題變?yōu)閺挠蚁陆堑阶笊辖?，只能向左和向上走，到達(dá)左上角是健康值最小且大于零
動(dòng)態(tài)規(guī)劃：
dp[i][j] = min(dp[i+1][j], dp[i][j+1])-dungeon[i][j]
但為了保證騎士始終活著，需要加一個(gè)約束
dp[i][j] = max(1,min(dp[i+1][j], dp[i][j+1])-dungeon[i][j])

代碼實(shí)現(xiàn)

class Solution(object):
    def calculateMinimumHP(self, dungeon):
        """
        :type dungeon: List[List[int]]
        :rtype: int
        """
        n = len(dungeon)
        m = len(dungeon[0])
        dp = [[float('Inf')]*(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]

本文鏈接：http://www.itdecent.cn/p/bc5f6951ce02