企业官网建设流程全解析

在⼀个 m*n 的棋盘的每⼀格都放有⼀个礼物，每个礼物都有⼀定的价值（价值⼤于 0）。你可以从棋盘的左
上⻆开始拿格⼦⾥的礼物，并每次向右或者向下移动⼀格、直到到达棋盘的右下⻆。给定⼀个棋盘及其上⾯
的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
输⼊:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出：12
解释：路径 1→3→5→2→1 可以拿到最多价值的礼物

classSolution:def__init__(self):self.memo=NonedefminPathSum(self,grid:List[List[int]])->int:m=len(grid)n=len(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 caseifi==0andj==0:returngrid[0][0]ifi<0orj<0: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]