建设部资质查询网站/危机舆情公关公司

64.最小路径和

解题思路：
利用动态规划的方法，建立一个与给定二维数组长度宽度相同的新数组，用来存放点点之间的最短距离。
紧接着利用题目给定的规则，路径每次只能从下方或者右方通过，因此可以得到以下方程：
当 i > 0 且 j = 0 时， dp[i][0] = dp[i - 1][0] + grid[i][0];

当 i = 0 且 j > 0 时， dp[0][j] = dp[0][j - 1] + grid[0][j];

当 i > 0 且 j > 0 时， dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j].

代码如下：

class Solution {public int minPathSum(int[][] grid) {if(grid == null | grid.length == 0 | grid[0].length == 0){return 0;    }int rows = grid.length;int columns = grid[0].length;int[][] dp = new int[rows][columns];dp[0][0] = grid[0][0];for(int i = 1;i < rows;i++){dp[i][0] = dp[i - 1][0] + grid[i][0];}for(int j = 1;j < columns;j++){dp[0][j] = dp[0][j - 1] + grid[0][j];}for(int i = 1;i < rows;i++){for(int j = 1;j < columns;j++){dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];}}return dp[rows - 1][columns - 1];}
}