在⼀个 m*n 的棋盘的每⼀格都放有⼀个礼物每个礼物都有⼀定的价值价值⼤于 0。你可以从棋盘的左上⻆开始拿格⼦⾥的礼物并每次向右或者向下移动⼀格、直到到达棋盘的右下⻆。给定⼀个棋盘及其上⾯的礼物的价值请计算你最多能拿到多少价值的礼物示例 1:输⼊:[[1,3,1],[1,5,1],[4,2,1]]输出12解释路径 1→3→5→2→1 可以拿到最多价值的礼物classSolution:def__init__(self):self.memoNonedefminPathSum(self,grid:List[List[int]])-int:mlen(grid)nlen(grid[0])# 构造备忘录初始值全部设为 -1self.memo[[-1for_inrange(n)]for_inrange(m)]returnself.dp(grid,m-1,n-1)defdp(self,grid:List[List[int]],i:int,j:int)-int:# base caseifi0andj0:returngrid[0][0]ifi0orj0:returnfloat(inf)# 避免重复计算ifself.memo[i][j]!-1:returnself.memo[i][j]# 将计算结果记入备忘录self.memo[i][j]max(self.dp(grid,i-1,j),self.dp(grid,i,j-1))grid[i][j]returnself.memo[i][j]