leetcode174. 地下城游戏

注意这题要反向思维，如果定义dp为到达i，j所需要的最小生命值的话是无法进行状态转移的,从前面的状态无法转移到后面
所以考虑从后往前的dp，定义dp为从i，j出发到达终点所需的最小生命值。
注意base case的两种写法，一种是直接写出来再循环里要跳过
第二种是改变base case 之前的一个状态，使其满足状态转移方程

def calculateMinimumHP(self, dungeon):
        """
        :type dungeon: List[List[int]]
        :rtype: int
        """
        #定义dp为从i，j到达终点所需的最小生命值
        #base dp[m][n] = 1 if dungeon[m][n] >= 0 else 1 - dungeon[m][n]
        #转移方程： dp[i][j] = min(dp[i+1][j], d[i][j+1]) - dungeon[i][j]
        m,n = len(dungeon),len(dungeon[0])
        dp = [[0x3f3f3f3f]*(n+1) for i in range(m+1)]
        #dp[m-1][n-1] = 1 if dungeon[m-1][n-1] >= 0 else 1 - dungeon[m-1][n-1] 
        dp[m-1][n] = 1

        for i in range(m-1,-1,-1):
            for j in range(n-1,-1,-1):
                # if i == m-1 and j == n-1:
                #     continue
                dp[i][j] = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]
                if  dp[i][j] <= 0:
                    dp[i][j] = 1
        return dp[0][0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21