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.

原题链接：https://oj.leetcode.com/problems/minimum-path-sum/

最短路径和。grid[i][j]保存每次能达到的最短路径和。

public class MinimumPathSum {
	public int minPathSum(int[][] grid) {
		int width = grid[0].length,height = grid.length;
		for(int i=1;i<width;i++)
			grid[0][i] += grid[0][i-1];
		for(int i=1;i<height;i++)
			grid[i][0] += grid[i-1][0];
		for(int i=1;i<height;i++){
			for(int j=1;j<width;j++)
				grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1]);
		}
		return grid[width-1][height-1];
	}
}

Minimum Path Sum