首页 > 代码库 > Minimum Path Sum
Minimum Path Sum
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.
用DP实现
找出递推关系和边界条件
1 public class Solution { 2 public int minPathSum(int[][] grid) { 3 if(1 == grid.length && 1 == grid[0].length) 4 return grid[0][0]; 5 int result[][] = new int[grid.length + 1][grid[0].length + 1]; 6 7 8 for(int i = 1; i <= grid.length; i++){ 9 for(int j = 1; j <= grid[0].length; j++){10 if(i == 1){11 result[i][j] = result[i][j - 1]; 12 }13 else if(j == 1)14 result[i][j] = result[i - 1][j];15 else16 result[i][j] = result[i - 1][j] <= result[i][j - 1] ? result[i - 1][j] : result[i][j - 1];17 result[i][j] += grid[i - 1][j - 1];18 }19 }20 21 return result[grid.length][grid[0].length];22 }23 }
Minimum Path Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。