首页 > 代码库 > LeetCode 64. Minimum Path Sum（最小和的路径）
LeetCode 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.
题目标签：Array
这道题目和前面两题差不多，基本思想都是一样的。这题要求我们找到最小和的路径。同样用Dynamic programming，我们可以分析一下，path 只能走右边和下面，那么对于每一个点，它的path 只可能从左边和上面来，我们只要在两者中取一个小的加上自己就可以了。因此，遍历gird，对于每一个点，有四种情况：
case 1：它有left 和top，取小的加上自己；
case 2：它只有left，left + 自己；
case 3：它只有top， top + 自己；
case 4：它没有left 和top，什么都不需要做。
最后返回终点的值就可以了。这里可以in-place， 也可以自己新建立一个matrix。
Java Solution:
Runtime beats 35.80%
完成日期：07/22/2017
关键词：Array
关键点：Dynamic Programming， 逆向思考
1 public class Solution 2 { 3 public int minPathSum(int[][] grid) 4 { 5 int rowSize = grid.length; 6 int colSize = grid[0].length; 7 8 9 for(int i=0; i<rowSize; i++) // row 10 { 11 for(int j=0; j<colSize; j++) // column 12 { 13 // if this point has both left and top 14 if(j-1 >=0 && i-1 >=0) 15 grid[i][j] += Math.min(grid[i][j-1], grid[i-1][j]); 16 else if(j-1 >=0) // if this point only has left 17 grid[i][j] += grid[i][j-1]; 18 else if(i-1 >=0) // if this point only has top 19 grid[i][j] += grid[i-1][j]; 20 // else, this point has no left and no top 21 22 } 23 } 24 25 return grid[rowSize-1][colSize-1]; 26 } 27 }
参考资料：N/A
LeetCode 算法题目列表 - LeetCode Algorithms Questions List
LeetCode 64. Minimum Path Sum（最小和的路径）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。