//time:o(mn)

//space:o(mn)

class Solution {

public int minPathSum(int[][] grid) {

int r = grid.length, c = grid[0].length;

if(grid == null || r == 0) return 0;

//dp for path sum

int dp[][] = new int[r][c];

//starting point

dp[0][0] = grid[0][0];

//next down move plus start point, tmp path sum

for(int i = 1; i < r; i++){

dp[i][0]=dp[i-1][0]+grid[i][0];

}

//next right move plus start point, tmp path sum

for(int j = 1; j < c; j++){

dp[0][j]=dp[0][j-1] + grid[0][j];

}

for(int i = 1; i < r; i++){

for(int j =1; j < c; j++){

dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];

}

}

return dp[r-1][c-1];

}

}