题目大意:从一个\(m \times n\)的格子左上角走到右下角，每个格子有一个非负整数，只能向右或者向下走，要找到一条路径使得格子里的数字的和最小？
这道题和62 63都比较相似，只是格子里面加了数字。跟骑士跟公主的那道题也相似。
1. 采用记忆化递归
class Solution(object):
def minPathSum(self, grid):
self.grid = grid
m = len(grid)
n = len(grid[0])
self.f = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
self.f[1][1] = grid[0][0]
def dp(y, x):
if x < 1 or y < 1:
return float('inf')
if y == 1 and x == 1:
return self.grid[0][0]
if self.f[y][x] > 0:
return self.f[y][x]
else:
self.f[y][x] = min(dp(y - 1, x), dp(y, x - 1)) + self.grid[y - 1][x - 1]
return self.f[y][x]
return dp(m, n)
2. 使用递推(动态规划)的办法，类似62题和63题：
class Solution(object):
def minPathSum(self, grid):
self.grid = grid
m = len(grid)
n = len(grid[0])
self.f = [[float('inf') for _ in range(n + 1)] for _ in range(m + 1)]
self.f[1][1] = grid[0][0]
def dp(y, x):
for y in range(1, m + 1):
for x in range(1, n + 1):
if y == 1 and x == 1:
continue
else:
self.f[y][x] = min(self.f[y - 1][x], self.f[y][x - 1]) + self.grid[y - 1][x - 1]
dp(m + 1, n + 1)
return self.f[m][n]
3. 使用递推，直接修改原矩阵
直接修改原来的矩阵grid，这样不会有额外的空间开销
class Solution(object):
def minPathSum(self, grid):
m = len(grid)
n = len(grid[0])
for y in range(m):
for x in range(n):
if y == 0 and x == 0:
continue
elif y == 0:
grid[y][x] += grid[y][x - 1]
elif x == 0:
grid[y][x] += grid[y - 1][x]
else:
grid[y][x] += min(grid[y][x - 1], grid[y - 1][x])
return grid[m - 1][n - 1]