建议先看这个题 这个题 这个题，再看这个题。

dfs

显然可以dfs，但是我们就不看了，因为大概率会超时。

动态规划

由于问题问初始的血量最低是多少，dp问题一般是最后一个状态作为输出值，所以对应的，应当从终点往起点迭代，最后输出dp[0][0]

其实状态转移方程改变不算大，但是规则比较的tricky，因为战士血量到0就死掉了，无法行动。所以在dp更新状态时要额外判断。

思路：
由于是从终点倒推起点，则dungeon的值实际应当在动态规划的时候反过来用，也就是原先减血的格子cost变成了buff，是给加血的；原先是加血的格子变成了减血的。
明白规则：在进入负值的格子的时候，战士血量在走出去时要>=1。
明白规则：在进入正值的格子的前，战士血量要至少1，而不是负值。

规则翻译到逆序倒推上：
若是此格子是正值

用M(i,j)代表在能成功踏过坐标i j格子的前提下，踏入格子前战士所需的最小血量，$reverse$代表加负号后的cost，根据规则，状态转移方程应该是：
s m a l l e r = m i n ( M ( i + 1 , j ) , M ( i , j + 1 ) ) M ( i , j ) = { 1 s m a l l e r + r e v e r s e i j < = 0 s m a l l e r + r e v e r s e i j else smaller=min(M(i+1,j),M(i,j+1))\\ M(i,j)=

smaller=min(M(i+1,j),M(i,j+1))M(i,j)={1smaller+reverseij​​smaller+reverseij​<=0else​
稍微解释下，$smaller$就是右侧和下侧那个方向上的血量更少。
case 分析：

• 当血量经过$reverse$后变成了负数或者0，则此格子原先是加血的，则战士最少只需血量1，活着到达这个格子，也就是dp[i][j]=1，而不是血量是负数/零的时候到达（正向看 这个血量已经挂了）。
• 当血量经过$reverse$后变成了正数，则此格子原先是减血的，则战士需要踏入格子前值变多才能蹚过这个格子，并且血量至少要变多$revers{e}_{ij}$，也就是dp[i][j]=smaller+reverse[i][j]。

代码：
pos_d是上文中的$reverse$，dungeon是$cost$，dp是$M$。

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        pos_d=[[-num for num in num_l] for num_l in dungeon]
        dp=[[0 for _ in pos_d[0]] for _ in pos_d]
        # print(pos_d)
        
        # 初始化
        i_max=len(pos_d)-1
        j_max=len(pos_d[0])-1
        dp[-1][-1]=pos_d[-1][-1]+1 if dungeon[-1][-1]<0 else 1
        # 从下往上初始化
        for i in range(i_max)[::-1]:
            # print(i)
            # print('dp[i+1][j_max]',dp[i+1][j_max],'pos_d[i][j_max]',pos_d[i][j_max])
            # print('dp[i+1][j_max]+pos_d[i][j_max]',dp[i+1][j_max]+pos_d[i][j_max])
            if dp[i+1][j_max]+pos_d[i][j_max]<=0:
                dp[i][j_max]=1
            else:
                dp[i][j_max]=dp[i+1][j_max]+pos_d[i][j_max]
        # 从右往左初始化
        for j in range(j_max)[::-1]:
            
            if dp[i_max][j+1]+pos_d[i_max][j]<=0:
                dp[i_max][j]=1
            else:
                dp[i_max][j]=dp[i_max][j+1]+pos_d[i_max][j]
        
        # print(dp)

        for i in range(i_max)[::-1]:
            for j in range(j_max)[::-1]:
                miner=min(dp[i+1][j],dp[i][j+1])
                if miner+pos_d[i][j]<=0:
                    dp[i][j]=1
                else:
                    dp[i][j]=miner+pos_d[i][j]
        
        # print(dp)
        return dp[0][0] # if dp[0][0]!=0 else 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

一共提交了3次，
第一次被dp[0][0]==0的时候错了。
第二次是在迭代更新dp的时候战士血量得大于0，我写成了等于0的时候也能走路了，错了。
第三次就AC了。

解题用时

60min，思路10分钟，debug50min， 惨。