leetcode hot100 64. 最小路径和 medium 递归优化

dfs(i, j) = 从 (0,0) 走到 (i,j) 的最小路径和

到 (i, j) 只能 ：向下 or 向右

dfs(i,j)=min(dfs(i+1,j),// 向下dfs(i,j+1)// 向右)+grid[i][j]

时间复杂度：O(m × n)
空间复杂度：O(m × n)

classSolution:defminPathSum(self,grid:List[List[int]])->int:# 时间复杂度：O(m × n)， 空间复杂度：O(m × n)m=len(grid)n=len(grid[0])@cache defdfs(i,j):# 当前位置(i,j)# 到达终点右下角ifi==m-1and j==n-1:returngrid[i][j]# 越界ifi>=m or j>=n:returnfloat('inf')# 向下 or 向右returngrid[i][j]+min(dfs(i+1,j),# 向下dfs(i,j+1)# 向右)returndfs(0,0)# 当前位置(i,j)从(0,0)开始