64. Minimum Path Sum

#### QUESTION:

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.

Example 1:

``````[[1,3,1],
[1,5,1],
[4,2,1]]
``````

Given the above grid map, return

``````7
``````

. Because the path 1→3→1→1→1 minimizes the sum.

#### EXPLANATION:

1，4，5

2，*,*

1也是同理，从上面来就是6，从左边来就是8，选择6。第二排就算出来了

2，7，6

if(i==0&&j==0)

f(i,j) = grid(0,0)

else{

f(i,j) = grid(i,j)+min(f(i-1,j),f(i,j-1))

}

#### SOLUTION:

``````class Solution {
public int minPathSum(int[][] grid) {
int[][] result = new int[grid.length][grid[0].length];
result[0][0] = grid[0][0];
for(int i = 0;i<grid.length;i++){
for(int j = 0;j<grid[i].length;j++){
int tmp = grid[i][j];
int m =0,n=0;
if(i-1<0&&j-1<0){
result[i][j] = tmp;
}else if(i-1>=0 && j-1<0){
m = result[i-1][j];
result[i][j] = tmp+m;
}else if(j-1>=0 && i-1<0){
n = result[i][j-1];
result[i][j] = tmp+n;
}else {
m = result[i-1][j];
n = result[i][j-1];
result[i][j] = tmp+Math.min(m,n);
}
}
}
return result[grid.length-1][grid[0].length-1];
}
}
``````
>