力扣100 92.最小路径和（动态规划）)
题解
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
数据范围
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j]<= 200
测试用例
示例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题解（时空omn）
classSolution{publicintminPathSum(int[][]grid){intm=grid.length;intn=grid[0].length;intdp[][]=newint[m][n];for(inti=0;i<m;i++){for(intj=0;j<n;j++){dp[i][j]=grid[i][j];if(i-1>=0&&j-1>=0)dp[i][j]+=Math.min(dp[i-1][j],dp[i][j-1]);elseif(i-1>=0&&j-1<0)dp[i][j]+=dp[i-1][j];elseif(i-1<0&&j-1>=0){dp[i][j]+=dp[i][j-1];}}}returndp[m-1][n-1];}}题解2（原地算法 时间同上，空间O1）
classSolution{publicintminPathSum(int[][]grid){intm=grid.length;intn=grid[0].length;for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(i==0&&j==0){continue;// 起点保持不变}elseif(i==0){// 只能从左边走过来 (第一行)grid[i][j]+=grid[i][j-1];}elseif(j==0){// 只能从上边走过来 (第一列)grid[i][j]+=grid[i-1][j];}else{// 取从上方和从左方过来的最小值，加上当前格子的值grid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1]);}}}returngrid[m-1][n-1];}}题解3（时间同上，空间On）
classSolution{publicintminPathSum(int[][]grid){intm=grid.length;intn=grid[0].length;int[]dp=newint[n];// 初始化第一个元素dp[0]=grid[0][0];// 初始化第一行for(intj=1;j<n;j++){dp[j]=dp[j-1]+grid[0][j];}for(inti=1;i<m;i++){// 每处理新的一行时，第一列只能由其正上方的值累加得到dp[0]+=grid[i][0];for(intj=1;j<n;j++){// dp[j] (上方的值) 和 dp[j-1] (左方的值) 进行比较dp[j]=Math.min(dp[j],dp[j-1])+grid[i][j];}}returndp[n-1];}}思路
这道题相当简单，博客中列出了两个相较于官解进阶一点空间复杂度，也不难。就不多讲了。
