Leetcode Link: 64. 最小路径和 - 力扣（LeetCode）
题目
给定一个包含非负整数的 _m_ x _n_ 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：次只能向下或者向右移动一步。
解法一
从暴力递归到动态规划
显然属于位置依赖的模型。
暴力递归
子函数参数为当前的位置 x，y
只有两种情况，左走或者下走，需要考虑边界
base case 是走到右下角而不是走出去！
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
@functools.lru_cache()
def process(x, y):
if x == len(grid)-1 and y == len(grid[0])-1:
return grid[x][y]
res = float('inf')
if y != len(grid[0])-1: # 边界判断
res = min(res, process(x, y+1) + grid[x][y])
if x != len(grid) - 1:
res = min(res, process(x+1, y) + grid[x][y])
return res
return process(0, 0)动态规划
该情况下，dp[x][y]表示的含义是从(x, y)到右下角的最小路径和
如果想直接想出dp，可以这样思考
dp[x][y]的含义再写一个新的代码：从(0, 0)到(x, y)的最小路径和
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
# [x, y]
dp = [[None for _ in range(len(grid[0]))] for _ in range(len(grid))]
# init
dp[len(grid)-1][len(grid[0])-1] = grid[len(grid)-1][len(grid[0])-1]
# 可以先写最后一行和最后一列
for x in range(len(grid)-2,-1,-1): # 最后一列
dp[x][len(grid[0])-1] = dp[x+1][len(grid[0])-1] + grid[x][len(grid[0])-1]
for y in range(len(grid[0])-2,-1,-1): # 最后一行
dp[len(grid)-1][y] = dp[len(grid)-1][y+1] + grid[len(grid)-1][y]
for x in range(len(grid)-2,-1,-1):
for y in range(len(grid[0])-2,-1,-1):
dp[x][y] = min(dp[x+1][y], dp[x][y+1]) + grid[x][y]
return dp[0][0]还可以进一步做状态压缩。