https://leetcode-cn.com/problems/minimum-path-sum/

idea

和三角形最小路径和类似 常规dp
首先 根据边界条件 直接可以确定第一行和第一列的最小路径
然后 依次遍历二维数组的每行
根据最小路径和 - 图1
即可轻松求解

遍历每i行的时候 第i-2行的数据没有意义 因此可以优化空间复杂度,这里没有做优化

Code

  1.     public static int minPathSum(int[][] grid) {
  2.         int result=0;
  3.         int m=grid.length; //m行
  4.         int n=grid[0].length; //n列
  5.         int[][] dp=new int[m][n];
  6.         int sum=0;
  7.         for(int i=0;i<m;i++)
  8.         {
  9.             sum+=grid[i][0];
  10.             dp[i][0]=sum;
  11.         }
  12.         sum=0;
  13.         for(int i=0;i<n;i++) {
  14.             sum += grid[0][i];
  15.             dp[0][i] = sum;
  16.         }
  17.         for(int i=1;i<m;i++)
  18.             for(int j=1;j<n;j++)
  19.             {
  20.                 if(dp[i][j-1]>dp[i-1][j])
  21.                 {
  22.                     dp[i][j]=dp[i-1][j]+grid[i][j];
  23.                 }
  24.                 else
  25.                     dp[i][j]=dp[i][j-1]+grid[i][j];
  26.             }
  27.         return dp[m-1][n-1];
  28.     }