?LeetCode刷題實(shí)戰(zhàn)174：地下城游戲
Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.
For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.
題意
解題
f(i,j)=max(0,min(f(i+1,j),f(i,j+1))?dungeon[i][j])
class Solution:
????def calculateMinimumHP(self, dungeon):
????????"""
????????:type?dungeon: List[List[int]]
????????:rtype: int
????????"""
????????row, col?= len(dungeon), len(dungeon[0])
????????mem = [[0]*col?for?_ in range(row)]
????????for?i in range(row-1,-1,-1):
????????????for?j?in range(col-1,-1,-1):
????????????????if?i == row-1?and?j?== col-1:
????????????????????mem[i][j] = max(0, -dungeon[i][j])
????????????????elif i == row-1:
????????????????????mem[i][j] = max(0, mem[i][j+1] - dungeon[i][j])
????????????????elif j?== col-1:
????????????????????mem[i][j] = max(0, mem[i+1][j] - dungeon[i][j])
????????????????else:
????????????????????mem[i][j] = max(0, min(mem[i+1][j], mem[i][j+1]) - dungeon[i][j])
????????????????
????????return?mem[0][0] + 1