1. Minimum Path Sum
求从m x n的matrix中的左上角到右下角的最小和，只能向右或下移动。
个人感觉这个题其实与全局比对算法很像，只是这个不用考虑左上角这个方向（不考虑斜着的情况）。以下是实现方法（未经优化）：
代码语言：javascript复制class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
path = [[0 for x in range(n)] for y in range(m)]
path[0][0] = grid[0][0]
for x in range(1,m):
path[x][0] = path[x-1][0] grid[x][0]
for y in range(1, n):
path[0][y] = path[0][y-1] grid[0][y]
for i in range(1, m):
for j in range(1, n):
path[i][j] = min(path[i-1][j], path[i][j-1]) grid[i][j]
return path[-1][-1]2. Minimum Falling Path Sum
与上题相似，不过这是一个方阵，并且下一行的所在的列必须与上一行的列不能超过一列。比如第一行第一列不能到第二行第三列（见例子）。
这个解题时需要考虑边界：
代码语言：javascript复制class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
path = [[0 for x in range(n)] for y in range(m)]
path[0][0] = grid[0][0]
for x in range(1,m):
path[x][0] = path[x-1][0] grid[x][0]
for y in range(1, n):
path[0][y] = path[0][y-1] grid[0][y]
for i in range(1, m):
for j in range(1, n):
path[i][j] = min(path[i-1][j], path[i][j-1]) grid[i][j]
return path[-1][-1]
