Leetcode 64. 最小路径和

心路历程：

第一反应像是一个回溯问题，但是看到题目中要求最值，大概率是一道DP问题。并且这里面的递推关系也很明显。
这里面边界条件可以有多种处理方法。

解法：动态规划

class Solution:def minPathSum(self, grid: List[List[int]]) -> int:m = len(grid)n = len(grid[0])dxy = [(1,0), (0,1)]@cachedef dp(i, j):if i == m-1 and j == n-1: return grid[i][j]candicate = []for each in dxy:nx, ny = i + each[0], j + each[1]if 0<= nx <= m-1 and 0 <= ny <= n-1:candicate.append([nx, ny])res = []for x, y in candicate:res.append(dp(x, y))return min(res) + grid[i][j]return dp(0,0)