package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://oj.leetcode.com/problems/triangle/
 */
public class Problem120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int result = 0;
        int idx = 0;
        for (int i = 0; i < triangle.size(); i++) {
            if (i == 0) {
                result = triangle.get(i).get(idx);
            } else {
                int a = triangle.get(i).get(idx);
                int b = triangle.get(i).get(idx+1);
                if (a <= b) {
                    result += a;
                } else {
                    result += b;
                    idx = idx + 1;
                }
            }
        }
        return result;
    }
    
    public static void main(String[] args) {
        Problem120 prob = new Problem120();
        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(Arrays.asList(2));
        triangle.add(Arrays.asList(3, 4));
        triangle.add(Arrays.asList(6, 5, 7));
        triangle.add(Arrays.asList(4, 1, 8, -3));
        System.out.println(prob.minimumTotal(triangle));
        
        triangle = new ArrayList<>();
        triangle.add(Arrays.asList(-1));
        triangle.add(Arrays.asList(2, 3));
        triangle.add(Arrays.asList(1, -1, -3));
        System.out.println(prob.minimumTotal(triangle));
    }
}
@@ -65,16 +65,46 @@
 Arrays;%0A
+import java.util.Collections;%0A
 import j
@@ -118,16 +118,16 @@
 l.List;%0A
-
 %0A/**%0A * 
@@ -271,22 +271,48 @@
     
-int result = 0
+List%3CInteger%3E result = new ArrayList%3C%3E()
 ;%0A  
@@ -321,147 +321,286 @@
     
+m
 in
-t idx = 0;%0A        for (int i = 0; i %3C triangle.size(); i++) %7B%0A       
+imumTotal(triangle, 0, 0, 0, result);%0A        return Collections.min(result);%0A    %7D%0A    %0A    private void minimumTotal(List%3CList%3CInteger%3E%3E triangle, int idx1, int idx2,%0A        int sum, List%3CInteger%3E result) %7B%0A
      
+   
 if (i
+dx1
  == 
-0) %7B%0A                result = triangle.get(i).get(idx
+triangle.size()) %7B%0A            result.add(sum
 );%0A 
@@ -606,32 +606,31 @@
             
-%7D else %7B
+return;
 %0A           
@@ -618,32 +618,34 @@
 return;%0A        
+%7D%0A
         int a = 
@@ -641,14 +641,17 @@
    i
-nt a =
+f (idx1 %3C
  tri
@@ -660,29 +660,18 @@
 gle.
-get(i).get(idx);%0A    
+size()) %7B%0A
     
@@ -683,14 +683,17 @@
    i
-nt b =
+f (idx2 %3C
  tri
@@ -707,21 +707,22 @@
 et(i
-).get(idx+1);
+dx1).size()) %7B
 %0A   
@@ -738,57 +738,108 @@
     
-if (a %3C= b) %7B%0A                    result += a;%0A  
+minimumTotal(triangle, idx1+1, idx2,%0A                    triangle.get(idx1).get(idx2)+sum, result);%0A
     
@@ -850,18 +850,9 @@
     
-  %7D else %7B
+%7D
 %0A   
@@ -864,81 +864,169 @@
     
-        result += b;%0A                    idx = idx + 1;%0A                %7D
+if (idx2+1 %3C triangle.get(idx1).size()) %7B%0A                minimumTotal(triangle, idx1+1, idx2+1,%0A                    triangle.get(idx1).get(idx2+1)+sum, result);
 %0A   
@@ -1050,31 +1050,8 @@
   %7D%0A
-        return result;%0A
     
@@ -1440,24 +1440,16 @@
 ngle));%0A
-        
 %0A       

Update problem 120 (it still fails on large datasets)