Python DP


  • 0
    class Solution(object):
        def calculateMinimumHP(self, dungeon):
            """
            :type dungeon: List[List[int]]
            :rtype: int
            """
            m, n = len(dungeon), len(dungeon[0])
            f = [[0] * n for _ in range(m)]
            f[-1][-1] = max(1,1-dungeon[-1][-1])
            for j in range(n-1,0,-1):
                f[-1][j-1] = max(1, f[-1][j] - dungeon[-1][j-1])
            for i in range(m-1,0,-1):
                f[i-1][-1] = max(1, f[i][-1] - dungeon[i-1][-1])
            for i in range(m-2,-1,-1):
                for j in range(n-2,-1,-1):
                    f[i][j] = min(max(1,f[i+1][j]-dungeon[i][j]), max(1,f[i][j+1]-dungeon[i][j]))
            return f[0][0]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.