最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
递归，核心是 minPathSum(grid) = min(self.minPathSum(leftGrid) + grid[m-1][n-1], self.minPathSum(upGrid) + grid[m-1][n-1])
class Solution: def minPathSum(self, grid: List[List[int]]) -> int: if not grid: return None; else: m = len(grid); n = len(grid[0]); if m > 1 and n > 1: leftGrid = [[0] * (n-1) for _ in range(m)] for i in range(m): for j in range(n-1): leftGrid[i][j] = grid[i][j] upGrid = [[0] * (n) for _ in range(m-1)] for i in range(m-1): for j in range(n): upGrid[i][j] = grid[i][j] return min(self.minPathSum(leftGrid) + grid[m-1][n-1], self.minPathSum(upGrid) + grid[m-1][n-1]) elif m == 1 and n > 1: leftGrid = [[0] * (n-1) for _ in range(m)] for i in range(m): for j in range(n-1): leftGrid[i][j] = grid[i][j] return self.minPathSum(leftGrid) + grid[m-1][n-1] elif m > 1 and n == 1: upGrid = [[0] * (n) for _ in range(m-1)] for i in range(m-1): for j in range(n): upGrid[i][j] = grid[i][j] return self.minPathSum(upGrid) + grid[m-1][n-1] elif m == 1 and n == 1: return grid[0][0]注： （1）二维数组必须被创建大小后使用，n为列，m-1为行 upGrid = [[0] * (n) for _ in range(m-1)]
还有一种方法，和上述方法基本一样，仅递归函数参数不同，前者为二维数组，后者为二维数组中的坐标
class Solution: def minPathSum(self, grid: List[List[int]]) -> int: def shortestPath(i, j): if (i >= 1) and (j >= 1): val = grid[i][j] + min(shortestPath(i-1, j), shortestPath(i, j-1)) elif (i == 0) and (j == 0): val = grid[0][0] elif i == 0: val = grid[i][j] + shortestPath(i, j-1) elif j == 0: val = grid[i][j] + shortestPath(i-1, j) return val return shortestPath(len(grid)-1, len(grid[0])-1)方法一是逆向思维，由右下角向上向左一层层进入函数 方法二是正向思维，从左上角向下向右一层层进入for循环，将每个grid[i][j]都修改为从grid[0][0]到该位置的最短距离 两者感觉运算量是一样的，但方法一超时，可能递归函数比较慢吧
class Solution: def minPathSum(self, grid: List[List[int]]) -> int: m = len(grid) n = len(grid[0]) for i in range(m): for j in range(n): if i == 0 and j == 0: grid[i][j] = grid[i][j] elif i == 0 and j != 0: grid[i][j] += grid[i][j-1] elif i != 0 and j ==0: grid[i][j] += grid[i-1][j] elif i != 0 and j != 0: grid[i][j] += min(grid[i][j-1], grid[i-1][j]) return grid[m-1][n-1]多阶段决策问题： 如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。
动态规划： 多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。 我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
二维数组自身作为备忘录dp[][]
class Solution { public int minPathSum(int[][] grid) { if(grid.length == 0 || grid[0].length == 0) return 0; int m = grid.length, n = grid[0].length; // 无需创建备忘录，自备忘 // 向前步进 for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(i == 0 && j == 0) grid[i][j] = grid[i][j]; else if(i == 0) grid[i][j] += grid[i][j-1]; else if(j == 0) grid[i][j] += grid[i-1][j]; else grid[i][j] += Math.min(grid[i][j-1], grid[i-1][j]); } } return grid[m-1][n-1]; } }