Leetcode 174. Dungeon Game

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

Interesting problem with classic DP solution. The better thought is start from end, and count each grid the min hp the hero needs to get through. The solution is using rolling DP with very elegant coding. Very impressive.

Solution:

# T:O(m*n) S:O(m+n)
class Solution:
    # @param dungeon, a list of lists of integers
    # @return a integer
    def calculateMinimumHP(self, dungeon):
        DP = [float("inf") for _ in dungeon[0]]
        DP[-1] = 1
        
        for i in reversed(xrange(len(dungeon))):
            DP[-1] = max(DP[-1] - dungeon[i][-1], 1)
            for j in reversed(xrange(len(dungeon[i]) - 1)):
                min_HP_on_exit = min(DP[j], DP[j + 1])
                DP[j] = max(min_HP_on_exit - dungeon[i][j], 1)
                
        return DP[0]

Run Time: 52 ms