Question
Formatted question description: https://leetcode.ca/all/64.html

```
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:
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
@tag-array
```

Algorithm
Code
Java

public class Minimum_Path_Sum {
public static void main ( String [] args ) {
Minimum_Path_Sum out = new Minimum_Path_Sum ();
Solution_recursion s = out . new Solution_recursion ();
System . out . println ( s . minPathSum ( new int [][]{ { 1 , 3 , 1 }, { 1 , 5 , 1 }, { 4 , 2 , 1 } }));
}
public class Solution {
public int minPathSum ( int [][] grid ) {
if ( grid . length == 0 || grid [ 0 ]. length == 0 ) {
return 0 ;
}
int m = grid . length ;
int n = grid [ 0 ]. length ;
// dp[i][j] meaning min-sum at (i,j)
int [][] dp = new int [ m ][ n ];
dp [ 0 ][ 0 ] = grid [ 0 ][ 0 ];
// pre-process, first row and col
for ( int j = 1 ; j < n ; j ++) {
dp [ 0 ][ j ] = dp [ 0 ][ j - 1 ] + grid [ 0 ][ j ];
}
for ( int i = 1 ; i < m ; i ++) {
dp [ i ][ 0 ] = dp [ i - 1 ][ 0 ] + grid [ i ][ 0 ];
}
for ( int i = 1 ; i < m ; i ++) {
for ( int j = 1 ; j < n ; j ++) {
dp [ i ][ j ] = grid [ i ][ j ] + Math . min ( dp [ i - 1 ][ j ], dp [ i ][ j - 1 ]);
}
}
return dp [ m - 1 ][ n - 1 ];
}
}
class Solution_recursion {
int min = Integer . MAX_VALUE ;
public int minPathSum ( int [][] grid ) {
if ( grid == null || grid . length == 0 || grid [ 0 ]. length == 0 ) {
return - 1 ;
}
dfs ( grid , 0 , 0 , 0 );
return min ;
}
private void dfs ( int [][] grid , int i , int j , int sum ) {
if ( i < 0 || j < 0 || i >= grid . length || j >= grid [ 0 ]. length ) {
// out of boundary
return ;
}
if ( i == grid . length - 1 && j == grid [ 0 ]. length - 1 ) {
// reaching termination position
min = Math . min ( sum + grid [ i ][ j ], min );
}
dfs ( grid , i + 1 , j , sum + grid [ i ][ j ]);
dfs ( grid , i , j + 1 , sum + grid [ i ][ j ]);
// actually, if detour is allowed, then should probe for all 4 directions, since maybe there is a Ingeter.MIN value
// dfs(grid, i + 1, j, sum + grid[i][j]);
// dfs(grid, i + 1, j, sum + grid[i][j]);
}
}
}