首页 > 其他 > 详细

LeetCode 63 Minimum Path Sum

时间:2014-09-01 22:52:23      阅读:259      评论:0      收藏:0      [点我收藏+]

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.

思路 :求grid[0][0]到grid[i][j]的最小和,就必须得出以下公式

bubuko.com,布布扣

public class Solution {
    public int minPathSum(int[][] grid) {
    	int i,j,min;
    	
    	for(i=1;i<grid.length;i++){
    		grid[i][0]+=grid[i-1][0];
    	}
    	for(i=1;i<grid[0].length;i++){
    		grid[0][i]+=grid[0][i-1];
    	}
    	
        for(i=1;i<grid.length;i++){
        	for(j=1;j<grid[0].length;j++){
        		min=grid[i-1][j]<grid[i][j-1]?grid[i-1][j]:grid[i][j-1];
        		grid[i][j]+=min;
        	}
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}


LeetCode 63 Minimum Path Sum

原文:http://blog.csdn.net/mlweixiao/article/details/38985871

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!