[DP][Path Sum][Triangle] Triangle

1. Example
Each step you may move to adjacent numbers on the row below.
[
     [2],
    [3,4],
  [6,5,7],
[4,1,8,3]
]
the minimum path sum from top to bottom is 11 (i.e.,   2+3+5+1 = 11)

2. Implementation
Q1: adjacent number ?
A1: last row i => next row i and i+1
Q1: minimum path , start from top, go left or go right
A1: e.g,, [2],
               [X,4]        1 from 0
               [2],
               [3,X]        0 from 0

               [3,X],      
               [6,X,X]    0 from 0
               [3,4],      
               [X,5,X]    1 from 0 or 1
               [X,4],      
               [X,X,7]    2 from 1
             
               [6,X,X],
               [4,X,X,X]   0 from 0
               [6,5,X],
               [X,1,X,X]     1 from 0 or 1
               [X,5,7],
               [X,X,8,X]     2 from 2 or 1
               [X,X,7],
               [X,X,X,3]      3 from 2
for every row you can keep a minimum
return sum so when return = > hit last row and last element
res[row.size()]

for (row =0 ~3)
 for ( i =0 ; i < row+1)
    i=0     res[ row ] += list.get(row).get(0) ,  min => res[row] = minimum
    i>0     min( res[row-1]+list.get(row).get(i),  row[row]+list.get(row).get(i) )
    i = row res[row-1]+list.get(row).get(row)

Q1: recursive?
A1:
1. base case                                   start > row's size => row+1,   row==last row return
2. for start from any point and      0 from 0, end from end-1, middle from middle or middle-1
combination sum, word breaker 1-D array
triangle => 2-D array

Q1: how to make it O(n)?
A1:

res[i] = res[i-1]+triangle.get(i).get(i);

res[0] = triangle.get(0).get(0);

 for (int i =1; i < triangle.size();i++)




//NOTE: res[i] in case the final res[0] value instead of the first one 

 //res[i] = res[i-1]+triangle.get(i).get(i); 

 res[0]+= triangle.get(i).get(0);





if (i == triangle.size()-1)
res[j] = triangle.get(i).get(j);

// Time:O(mxn), Space:O(n) rowNumbers
// NOTE: int[][] is a square array or fixed size 
// for size not determined use List>
public int minimumTotal(List> triangle)
{
     

      // invalidate the input
      if ( triangle == null || triangle.size() == 0)
      {
          return 0; // since all positive numbers
      }




      // NOTE: size() =1, avoid the below computation
      if ( triangle.size() == 1)
         return triangle.get(0).get(0);




      
      //int[] res = new int[triangle.size()];
      //res[0] = triangle.get(0).get(0);
      //for (int i = 1 ;i < triangle.size();i++)
      //{
      //    res[i] = res[i-1] + triangle.get(i).get(0);
      //}
      
      // NOTE: how to use a array to represent first index and last index at the same time, so res[row.size()] ides WRONG!
      // NOTE: WE can brute force like minimum path sum, but time complexity would be O(mxn), which means need for for loop
        


      // Must go to leaves, 4 minimum value , an array of size 4
      int[] res = new int[triangle.size()];
      // NOTE: merge
      //for (int i =0 ; i < triangle.size();i++)
      //{
      //    res[0]+= triangle.get(i).get(0);
      //}
      
   


      res[0] = triangle.get(0).get(0);
      for (int i =1; i < triangle.size();i++)
      //for (int i = 0 ; i < triangle.size()-1; i++)
      {
 


         
         res[i] = res[i-1]+triangle.get(i).get(i);





         //for (int j = 1 ; j < triangle.get(i).size()-1; j++)
         //for (int j = 1 ; j < i-1; j++)
         for (int j = i-1 ; j >= 1; j--)
             res[j] = Math.min(res[j], res[j-1] ) + triangle.get(i).get(j);  




         //NOTE: res[i] in case the final res[0] value instead of the first one 
         //res[i] = res[i-1]+triangle.get(i).get(i);
         res[0]+= triangle.get(i).get(0);



      
     }
      


      // NOTE: Merge
      ////for (int i=0; i < triangle.size();i++)
      // for (int i=1; i < triangle.size();i++)
      //{
      ////     res[i] += triangle.get(i).get(i);
      //       res[i] = res[i-1]+triangle.get(i).get(i);// previous row so res[i-1]
      //}




      //int min = Integer.MAX_VALUE;
      int min = res[0];
      //for (  int i = 0; i < triangle.size(); i++)
      for (int i =1 i < triangle.size();i++)
      {
           if (res[i] < min)
              min = res[i];
      }
     



      return min;




}

// Bottom-Up    Time:O(mxn), Space:O(n) res array
public int minimumTotal(List> triangle)
{
      




      // validate the input
      if ( triangle == null || triangle.length == 0)
      {
          return 0;// since all positive numbers
      }





      int[] res = new int[triangle.size()];
      for (int i = triangle.size()-1; i>=0; i--)
      {
           for (int j = i; j > = 0; j--)
           {
                if (i == triangle.size()-1)
                   res[j] = triangle.get(i).get(j);

                res[j] = Math.min( res[j], res[j+1] ) + triangle.get(i).get(j);
           }
      }



            
      return res[0];


}
i = 3
res[3]  =3
res[2]  =8
res[1]  =1
res[0]  =4
i = 2
res[2]  = min(res[2],res[3]) +7 = 10
res[1]  = min(res[1],res[2]) +5 = 6
res[0]  = min(res[0],res[1]) +6 = 7
i = 1
res[1]  = min(res[1], res[2]) + 4 = 10
res[0]  = min(res[0], res[1]) + 3 = 9
i=0
res[0] = min(res[0],res[1]) +2 = 11


Recursive Idea:
1.Base i i) helper(i+1,j)
2.for (j)
helper(i,j)

3. Similar Ones
path sum + minimum + continue => DP
1-D DP
[
Unique Path I and II
Minimum Path Sum
Buy and Sell stock at the Best Time
Maximum Subarray
]
Path Sum series
Triangle Series