[DP][Min][Path Sum] Minimum Path Sum

1. Example
[
[1,5,5]
[1,1,5]
[7,1,1]
]

minimum path =
[
[1,5,5]
[1,1,5]
[7,1,1]
]
Return sum = 5

2. Implementation
Q1: can we use the idea got from Unique Path?
A1: they use res[j] = res [j] + res[j-1] or 0 (if obstacle). We can just change total path number value into current cell value.
Q1: Still only move down or right, and how to formulate?
A1: path sum = res [i,j] = Math.max( res[i-1,j] + grid[i][j] , res[i][j-1] +grid[i][j] )
Q1: could have a case, current grid cell value is greater than previous sum?
A1: no worry, since assume non-negative number . so will only become larger and larger when move to current grid cell and add into path sum
Q1: if res[i,j] , the complexity for Time:O(mxn) and Space:O(mxn), any improvement?
A1: res[i] = min (   res[i-1] + grid[i][j],   res[i]+grid[i][j]   )
[
[1,5,5]
[1,1,5]
[7,1,1]
]
row =0
res[0] =1
res[1] =5
res[2] =5
row =1
res[0] = 1+1 =2
res[1] = min( res[0]+1, res[1]+1  ) = min(3,6) = 3
res[2] = min(res[1]+5, res[2]+5) = min(8, 10) = 8
row =2
res[0]= res[0]+7 = 9
res[1]=min(res[0]+1, res[1]+1) = min(10,4) =4
res[2] = min(res[1]+1, res[2]+1) = min(5,9)=5
return 5

Q1 :recursive?
A1:unique path  helper(i+1,j) + helper(i,j+1) ===>
                 min (  helper(i+1,j) +grid[i,j],   helper(i,j+1) + grid[i][j] )
 and base case would be i == m- 1 && j == n-1 return value otherwise return MAX
[
[1,5,5]
[1,1,5]
[7,1,1]
]
helper(0,0)
helper(1,0)+ 1,                                                                                helper(0,1)+1
    helper(2,0) + 1,                              helper(1,1) +1                        helper(1,1)+5,      helper(0,2)+5
    h(3,0)X+7, h(2,1)+7                      h(2,1)+1, h(1,2)+1
                       h(3,1)X+1 h(2,2)+1 ! h(3,1)X+1, h(2,2)+1

// NOTE: res[j] = min(res[j]+cell , res[j-1]+cell) i >1, so we init j = 0 first

// NOTE: if loop from i = 0, init value for all res array is 0 and could get wrong minimum value

//NOTE: Base Case

 if ( i > grid.length -1 || j > grid[0].length -1) 

return Integer.MAX_VALUE;

 if ( i == grid.length-1 && j == grid[0].length-1) 

{ return sum + grid[i][j]; //return grid[i][j]; }

// DP 
// prev info + base case + init value
// Time :O(mxn) all cells, Space:O(n) array
public int minPathSum(int[][] grid)
{
    // validate the input
    if ( grid == null || grid.length ==0 || grid[0].length==0  )
    {
         return 0; // since all positive number
    }






    int[] res = new int[grid[0].length];
    // NOTE: res[j] = min(res[j]+cell , res[j-1]+cell) i >1, so we init j = 0 first
    res[0] = grid[0][0];
    //for (int j = 0 ; j < grid[0].length; j++)
    for (int j =1; j < grid[0].length; j++)
    {
         //res[j] = grid[0][j];
         res[j] = res[j-1] + grid[0][j];
    }




    // NOTE: if loop from i = 0, init value for all res array is 0 and could get wrong minimum value
    for (int i = 1 ; i <  grid.length ;i++)
        for ( int j = 0; j < grid[0].length;j++ )     
            res[j] = (j==0)? res[j] + grid[i][j]: Math.min( res[j-1], res[j] ) + grid[i][j];




    
    return res[grid[0].length -1];




}

public int minPathSum(int[][] grid)
{
     //validate the input
     if ( grid == null || grid[0].length == 0 || grid.length == 0)
     {
          return 0; // since all positive numbers
     }
     

     return helper(0,0,grid,0);


}
private int helper(int i, int j, int[][] grid, int sum)
//private int helper(int i, int j, int[][] grid)
{
     // validate the input
     ..





     // Base Case
     if ( i > grid.length -1 || j > grid[0].length -1)
        return Integer.MAX_VALUE;
     if ( i == grid.length-1 && j == grid[0].length-1)
     {
         
         return sum + grid[i][j];
         //return grid[i][j];
     } 





     return Math.min(  helper(i+1, j, grid, sum+grid[i][j]), helper(i,j+1, grid, sum+grid[i][j])    );
     //return Math.min(   helper(i+1,j,grid),helper(i,j+1, grid)  ) + grid[i][j];





}
helper(0,0)
h(1,0, "1"), h(0,1, "1")
h(2,0, "1,1"),h(1,1, "1,1")
              h(2,1,"1,1,1") h(1,2,"1,1,1")
              h(2,2,"1,1,1,1"), h(3,1)
              return "1,1,1,1,1" ,  return"MAX" ==> "1,1,1,1,1"

3. Similar Ones
DP= grid + max or min

(M)          Unique Paths I/II
(H)           Dungeon Game
[Tree]       Path Sum
[Tree]       Path Sum II
[Tree]       Binary Tree Maximum Path Sum
[Tree]       Sum Root to Leaf Numbers