public class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        //let dp[i][j] denotes the minimum sum from (0,0) to (i,j)
        dp[0][0]=grid[0][0];
        int m = grid.length, n = grid[0].length;
        //initilize the first row and column
        for (int row=1;row<grid.length;row++)
            dp[row][0]+=dp[row-1][0]+grid[row][0];
        for (int col=1;col<grid[0].length;col++)
            dp[0][col]+=dp[0][col-1]+grid[0][col];

        for (int i=1;i<grid.length;i++)
            for(int j=1;j<grid[0].length;j++){
                dp[i][j]=grid[i][j]+Math.min(dp[i-1][j],dp[i][j-1]);
            }

        return dp[m-1][n-1];
    }
}