目录
1、题目2、思路、c++代码4、java代码
1、题目
给定一个包含非负整数的mxn网格grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例1：
输入：grid=[[1,,1],[1,5,1],[4,2,1]]输出：7解释：因为路径1→→1→1→1的总和最小。
示例2：
输入：grid=[[1,2,],[4,5,6]]输出：12
提示：
m==grid.lengthn==grid.length1=m,n==grid[j]=
2、思路
(动态规划)O(mn)O(m*n)O(mn)
状态表示：f[i,j]表示从(0,0)走到(i,j)的最小路径和。那么，f[n-1][m-1]就表示从网格左上角到网格右下角的最小路径和，即为答案。
状态转移：
由于限制了只会向下走或者向右走，因此到达(i,j)有两条路径
从上方转移过来，f[j]=f[i-1][j]+grid[j]从左方转移过来，f[j]=f[j-1]+grid[j]
因此，状态计算方程为：f[j]=max(f[i-1][j],f[j-1])+grid[j]，从向右和向下两条路径中选择路径之和最小的转移过来，再加上grid[j]的值。
初始化条件：f[0][0]=grid[0][0]，其余都初始化为正无穷。
分析图示：
时间复杂度分析：O(mn)O(m*n)O(mn)，其中mmm和nnn分别是网格的行数和列数。
、c++代码
classSolution{public:intminPathSum(vectorvectorintgrid){intn=grid.size();intm=grid[0].size();vectorvectorintf(n,vectorint(m,INT_MAX));for(inti=0;in;i++)for(intj=0;jm;j++){if(!i!j)f[j]=grid[j];//初始化f[0][0]=grid[0][0]else{if(i)f[j]=min(f[j],f[i-1][j]+grid[j]);//如果可以从上方转移过来if(j)f[j]=min(f[j],f[j-1]+grid[j]);//如果可以从左方转移过来}}turnf[n-1][m-1];}};
4、java代码
classSolution{publicintminPathSum(int[][]grid){intn=grid.length;intm=grid[0].length;int[][]f=newint[n][m];for(inti=0;in;i++)for(intj=0;jm;j++){if(i==0j==0)f[j]=grid[j];//初始化f[0][0]=grid[0][0]else{f[j]=0xffff;if(i0)f[j]=Math.min(f[j],f[i-1][j]+grid[j]);//如果可以从上方转移过来if(j0)f[j]=Math.min(f[j],f[j-1]+grid[j]);//如果可以从左方转移过来}}turnf[n-1][m-1];}}
原题链接：64.最小路径和
,