174. 地下城游戏 -- 动规

174. 地下城游戏

class CalculateMinimumHP:"""174. 地下城游戏https://leetcode.cn/problems/dungeon-game/"""def solution(self, dungeon: List[List[int]]) -> int:# 我们想计算左上⻆到右下⻆所需的最⼩⽣命值m, n = len(dungeon), len(dungeon[0])self.memo = [[-1 for _ in range(n)] for _ in range(m)]return self.dp(dungeon, 0, 0)def dp(self, grid, i, j):"""从 grid[i][j] 到达终点（右下⻆）所需的最少⽣命值:param grid::param i::param j::return:"""m, n = len(grid), len(grid[0])# base caseif i == m - 1 and j == n - 1:return 1 if grid[i][j] >= 0 else -grid[i][j] + 1if i == m or j == n:return float('inf')if self.memo[i][j] != -1:return self.memo[i][j]res = min(self.dp(grid, i, j+1),self.dp(grid, i+1, j)) - grid[i][j]self.memo[i][j] = 1 if res <= 0 else resreturn self.memo[i][j]