Problem Description:

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

Solution:

1     public int minimumTotal(List
     
      
       > triangle) { 2         for (int i = triangle.size()- 1; i >= 0; i--) { 3             minimumTriangle(triangle, i); 4         } 5         return triangle.get(0).get(0); 6     } 7      8     public void minimumTriangle(List
       
        
         > triangle, int row) { 9         if (row == triangle.size() - 1)10             return;11         int min = Integer.MAX_VALUE;12         for (int i = 0; i < triangle.get(row).size(); i++) {13             triangle.get(row).set(i, triangle.get(row).get(i) + Math.min(triangle.get(row+1).get(i), triangle.get(row+1).get(i+1)));14         }15     }