{"id":3481,"date":"2020-05-03T11:52:34","date_gmt":"2020-05-03T03:52:34","guid":{"rendered":"http:\/\/www.sniper97.cn\/?p=3481"},"modified":"2020-05-03T11:52:34","modified_gmt":"2020-05-03T03:52:34","slug":"%e3%80%90leetcode%e3%80%91l0174-%e5%9c%b0%e4%b8%8b%e5%9f%8e%e6%b8%b8%e6%88%8f","status":"publish","type":"post","link":"http:\/\/www.sniper97.cn\/index.php\/note\/algorithm\/3481\/","title":{"rendered":"\u3010LeetCode\u3011*0174 \u5730\u4e0b\u57ce\u6e38\u620f"},"content":{"rendered":"\n

https:\/\/leetcode-cn.com\/problems\/dungeon-game\/<\/a><\/p>\n\n\n

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

\"\"\"
<\/em>      \u250f\u251b \u253b\u2501\u2501\u2501\u2501\u2501\u251b \u253b\u2513
<\/em>      \u2503<\/em>\u3000\u3000\u3000\u3000\u3000\u3000<\/em> \u2503
<\/em>      \u2503<\/em>\u3000\u3000\u3000<\/em>\u2501<\/em>\u3000\u3000\u3000<\/em>\u2503
<\/em>      \u2503<\/em>\u3000<\/em>\u2533\u251b<\/em>\u3000<\/em>  \u2517\u2533<\/em>\u3000<\/em>\u2503
<\/em>      \u2503<\/em>\u3000\u3000\u3000\u3000\u3000\u3000<\/em> \u2503
<\/em>      \u2503<\/em>\u3000\u3000\u3000<\/em>\u253b<\/em>\u3000\u3000\u3000<\/em>\u2503
<\/em>      \u2503<\/em>\u3000\u3000\u3000\u3000\u3000\u3000<\/em> \u2503
<\/em>      \u2517\u2501\u2513<\/em>\u3000\u3000\u3000<\/em>\u250f\u2501\u2501\u2501\u251b
<\/em>        \u2503<\/em>\u3000\u3000\u3000<\/em>\u2503   <\/em>\u795e\u517d\u4fdd\u4f51<\/em>
<\/em>        \u2503<\/em>\u3000\u3000\u3000<\/em>\u2503   <\/em>\u4ee3\u7801\u65e0<\/em>BUG<\/em>\uff01<\/em>
<\/em>        \u2503<\/em>\u3000\u3000\u3000<\/em>\u2517\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2513
<\/em>        \u2503<\/em>\u3000\u3000\u3000\u3000\u3000\u3000\u3000<\/em>    \u2523\u2513
<\/em>        \u2503<\/em>\u3000\u3000\u3000\u3000<\/em>         \u250f\u251b
<\/em>        \u2517\u2501\u2513 \u2513 \u250f\u2501\u2501\u2501\u2533 \u2513 \u250f\u2501\u251b
<\/em>          \u2503 \u252b \u252b   \u2503 \u252b \u252b
<\/em>          \u2517\u2501\u253b\u2501\u251b   \u2517\u2501\u253b\u2501\u251b
<\/em>\"\"\"
<\/em>
<\/em>
<\/em>class Solution(object):
    def calculateMinimumHP(self, dungeon):
        \"\"\"
<\/em>        <\/em>:type<\/em><\/strong> dungeon: List[List[int]]
<\/em>        <\/em>:rtype<\/em><\/strong>: int
<\/em>        \"\"\"
<\/em>        <\/em>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
<\/pre>\n\n\n
\u601d\u8def<\/strong>\uff1a\u8fd9\u9053\u9898\u7b2c\u4e00\u773c\u770b\u5230\u5c31\u662fdp\uff0c\u4f46\u662f\u8fd9\u9053\u9898\u3002\u3002\u5b83dp\u7684\u4e0d\u4e00\u6837\u3002<\/p>\n\n\n
\u8fd9\u9053\u9898\u9700\u8981\u4f7f\u7528\u53cd\u5411dp\uff0c\u539f\u56e0\u5c31\u662f\u5bf9\u4e8e\u5f53\u524d\u7684\u6700\u4f18\u72b6\u6001\uff0c\u7531\u4e8e\u4e0b\u4e00\u4f4d\u7f6e\u53d6\u51b3\u4e8e\u5f53\u524d\u4f4d\u7f6e\u7684\u5269\u4f59\u8840\u91cf\uff0c\u4e3e\u4e2a\u4f8b\u5b50\uff0cA\u8def\u5f84\u5230\u8fd9\u91cc\u5269\u4f59\u8840\u91cf\u4e3a5\uff0c\u800cB\u8def\u5f84\u5269\u4f59\u8840\u91cf\u4e3a0\uff0c\u540c\u65f6B\u8def\u5f84\u6bd4A\u8def\u5f84\u66f4\u4f18\uff08\u5bf9\u4e8e\u5f53\u524d\u7ed3\u70b9\u6765\u8bf4\uff09\uff0c\u800c\u5bf9\u4e8e\u4e0b\u4e00\u4e2a\u7ed3\u70b9\uff0cA\u5f88\u53ef\u80fd\u4f9d\u636e\u5f53\u524d\u5269\u4f59\u8840\u91cf\u4f18\u52bf\u53cd\u8d85B\u7684\u6548\u679c\uff0c\u56e0\u6b64\u6b63\u5411dp\u53d8\u5f97\u4e0d\u53ef\u884c\u3002<\/p>\n\n\n
\u56e0\u6b64\u4f7f\u7528\u53cd\u5411dp\uff0c\u4ece\u7ed3\u679c\u5411\u5f00\u59cbdp\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
https:\/\/leetcode-cn.com\/problems\/dungeon-game\/ # – […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_mi_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[10],"tags":[],"views":5410,"_links":{"self":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/3481"}],"collection":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/comments?post=3481"}],"version-history":[{"count":0,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/3481\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/media?parent=3481"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/categories?post=3481"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/tags?post=3481"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}