Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [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).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Hint: use dynamic programming. However, instead of using n arrays which in total cost n^2 space, we just use 2 arrays interchangeably to store the minimum path sum until the current row.

01 public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
02     // Start typing your Java solution below
03     // DO NOT write main() function
04     int size=triangle.size();
05     if(size==0)
06         return 0;
07     //get the numbers of each row in the original triangle
08     ArrayList<Integer> row=triangle.get(0);
09   
10     //keeps the minimum path sum to reach each node of the current line
11     //starts from the 0-th line
12     ArrayList<Integer> al=new ArrayList<Integer>();
13     al.add(row.get(0));
14     if(size==1)
15         return al.get(0);
16   
17     //Iterate from the 1-st line
18     for(int i=1;i<size;i++)
19     {
20        //keep the numbers of the previous line in al
21        //use another array al2 to calculate the new path sum
22        //then copy the new result in al2 back to al
23         ArrayList<Integer> al2=new ArrayList<Integer>();
24         for(int k=0;k<al.size();k++)
25         {
26             al2.add(al.get(k));
27         }
28       
29         row=triangle.get(i);          
30         int lmost=row.get(0)+al.get(0);
31         al2.set(0,lmost);
32         for(int j=1;j<i;j++)
33         {
34             //minimum of the left index and itself in the previous line
35             //plus its own value
36             int value=Math.min(al.get(j-1),al.get(j))+row.get(j);
37             al2.set(j,value);
38         }
39         int rmost=al.get(i-1)+row.get(i);
40         al2.add(rmost);
41         al=al2;
42     }
43   
44     //find min
45     int min=al.get(0);
46     for(int i=0;i<al.size();i++)
47     {
48         if(al.get(i)<min)
49         {
50             min=al.get(i);
51         }
52     }
53   
54     return min;
55           
56 }