动态规划算法-路径问题：9.最小路径和

题目链接：64. 最小路径和（中等）

算法原理：

解法：动态规划

4ms击败21.82%

时间复杂度O(mn)

①状态表示：

dp[i][j]：到达(i,j)位置时的最小路径和

②状态转移方程：

从左侧转移而来：

dp[i][j]=dp[i][j-1]+g[i][j]

从上方转移而来：

dp[i][j]=dp[i-1][j]+g[i][j]

因此dp[i][j]=min(从左侧来，从右侧来)

③初始化：

多开一行一列

dp[0][1]=dp[1][0]=0

④填表顺序：

每行从上往下，每行从左往右

⑤返回值：

dp[m][n]

Java代码：

class Solution { //64. 最小路径和 public int minPathSum(int[][] grid) { int m=grid.length,n=grid[0].length; int[][] dp=new int[m+1][n+1]; for(int i=0;i<dp.length;i++) Arrays.fill(dp[i],Integer.MAX_VALUE); dp[0][1]=dp[1][0]=0; 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-1][j-1]; } } return dp[m][n]; } }