首页 > 代码库 > 64. Minimum Path Sum
64. Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
本题和triangle比较相似,只不过从三角形变成了矩形,但是方法还是一样的,同样是用dp解决,代码如下:
1 public class Solution { 2 public int minPathSum(int[][] grid) { 3 if(grid==null||grid.length==0||grid[0].length==0) return 0; 4 int m = grid.length; 5 int n =grid[0].length; 6 int[][] dp = new int[m][n]; 7 dp[0][0] = grid[0][0]; 8 for(int i=1;i<m;i++){ 9 dp[i][0] = dp[i-1][0]+grid[i][0]; 10 } 11 for(int i=1;i<n;i++){ 12 dp[0][i] = dp[0][i-1]+grid[0][i]; 13 } 14 for(int i=1;i<m;i++){ 15 for(int j=1;j<n;j++){ 16 dp[i][j] =grid[i][j]+Math.min(dp[i][j-1],dp[i-1][j]); 17 } 18 } 19 return dp[m-1][n-1]; 20 } 21 }
64. Minimum Path Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。