一、题目描述
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 100
二、思路讲解
2.1、暴力搜索（超时）
看到二维数组的题，我会先考虑能不能暴力搜索，思路是找自己右方和下方更小的那条路。
class Solution { int [][]grid; public int minPathSum(int[][] grid) { this.grid = grid; return dfs(0, 0); } int dfs(int i, int j) { if(i==grid.length-1 && j==grid[0].length-1) { return grid[i][j]; } if(i==grid.length-1) { return dfs(i, j+1) + grid[i][j]; } if(j==grid[0].length-1) { return dfs(i+1, j) + grid[i][j]; } return Math.min(dfs(i, j+1), dfs(i+1, j)) + grid[i][j]; } }
2.2、动态规划（二维dp数组）
既然dfs行不通，那我们就试试dp。不难看出，走到每个位置的路径和取决于他上方的格子的路径和 or 左方格子的路径和，因此我们用dp[ i ][ j ]来表示走到（i，j）位置的最小路径和，易得递推公式：dp[i][j] = min{ dp[i-1][j] , dp[i][j-1] } + grid[i][j]
class Solution { public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; int [][]dp = new int[m][n]; dp[0][0] = grid[0][0]; for(int i=1; i<m; i++) { dp[i][0] = dp[i-1][0] + grid[i][0]; } for(int i=1; i<n; i++) { dp[0][i] = dp[0][i-1] + grid[0][i]; } for(int i=1; i<m; i++) { for(int j=1; j<n; j++) { dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j]; } } return dp[m-1][n-1]; } }
2.3、动态规划（一维dp数组）
接下来我们就来思考如何优化空间。画图可得，我们在动态规划时，是按照一行一行逐步dp的，下一行的值只由上一行和当前行决定，所以我们可以只保留上一行的数据，这样只需要用到一维数组。
这样的优化思路可参考：告别动态规划，连刷 40 道题，我总结了这些套路，看不懂你打我（万字长文） - 知乎
class Solution { public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; int []dp = new int[n]; dp[0] = grid[0][0]; for(int i=1; i<n; i++) { dp[i] = dp[i-1] + grid[0][i]; } for(int i=1; i<m; i++) { dp[0] = dp[0] + grid[i][0]; for(int j=1; j<n; j++) { dp[j] = Math.min(dp[j-1], dp[j]) + grid[i][j]; } } return dp[n-1]; } }
2.4、动态规划（不使用额外空间）
接2.2的思路，我们其实可以在原数组上直接修改，这样就不使用额外空间了。不过面试的时候有可能会要求不能更改原数组，这种情况下2.3是最优的思路。
