/**
 *	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.	
 *
 *	Author: matao
 *
 */

public class MinimumPathSum {
	public int minPathSum(int[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length, columns = grid[0].length;

        int[][] result = new int[rows][columns];
        result[0][0] = grid[0][0];

        for(int i = 1; i < rows; i++) {
            result[i][0] = result[i-1][0] + grid[i][0];
        }

        for(int i = 1; i < columns; i++) {
            result[0][i] = result[0][i-1] + grid[0][i];
        }

        for(int i = 1; i < rows; i++) {
            for(int j = 1; j < columns; j++) {
                result[i][j] = (result[i][j-1] < result[i-1][j] ? result[i][j-1] : result[i-1][j]) + grid[i][j];
            }
        }
        return result[rows-1][columns-1];
    }
}
@@ -298,16 +298,23 @@
 %09public 
+static 
 int minP
@@ -1070,10 +1070,427 @@
 %5D;%0A    %7D
+%0A%0A    public static void main(String%5B%5D args) %7B%0A    %09int%5B%5D%5B%5D grid1 = %7B%7B1, 2%7D,%0A    %09%09%09%09%09 %7B1, 1%7D%7D;%0A    %09System.out.println(minPathSum(grid1));%0A%0A    %09int%5B%5D%5B%5D grid2 = null;%0A    %09System.out.println(minPathSum(grid2));%0A%0A    %09int%5B%5D%5B%5D grid3 = %7B%7B2, 3, 1%7D%7D;%0A    %09System.out.println(minPathSum(grid3));%0A%0A    %09int%5B%5D%5B%5D grid4 = %7B%7B2, 3, 1%7D,%0A    %09%09%09%09%09 %7B1, 2, 1%7D,%0A    %09%09%09%09%09 %7B3, 5, 1%7D%7D;%0A    %09System.out.println(minPathSum(grid4));%0A    %7D
 %0A%7D

add test case