package leetcode;

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

/**
 * https://oj.leetcode.com/problems/triangle/
 */
public class Problem120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        List<Integer> result = new ArrayList<>();
        minimumTotal(triangle, 0, 0, 0, result);
        return Collections.min(result);
    }
    
    private void minimumTotal(List<List<Integer>> triangle, int idx1, int idx2,
        int sum, List<Integer> result) {
        if (idx1 == triangle.size()) {
            result.add(sum);
            return;
        }
        if (idx1 < triangle.size()) {
            if (idx2 < triangle.get(idx1).size()) {
                minimumTotal(triangle, idx1+1, idx2,
                    triangle.get(idx1).get(idx2)+sum, result);
            }
            if (idx2+1 < triangle.get(idx1).size()) {
                minimumTotal(triangle, idx1+1, idx2+1,
                    triangle.get(idx1).get(idx2+1)+sum, 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));
    }
}
@@ -33,72 +33,15 @@
 til.
-ArrayList;%0Aimport java.util.Arrays;%0Aimport java.util.Collections
+HashMap
 ;%0Aim
@@ -60,16 +60,38 @@
 il.List;
+%0Aimport java.util.Map;
 %0A%0A/**%0A *
@@ -232,21 +232,28 @@
         
-List%3C
+Map%3CString, 
 Integer%3E
@@ -257,30 +257,26 @@
 er%3E 
-result
+memo
  = new 
-ArrayList
+HashMap
 %3C%3E()
@@ -277,32 +277,39 @@
 ap%3C%3E();%0A        
+return 
 minimumTotal(tri
@@ -325,57 +325,12 @@
  0, 
-0, result);%0A        return Collections.min(result
+memo
 );%0A 
@@ -351,20 +351,19 @@
 private 
-void
+int
  minimum
@@ -406,22 +406,20 @@
 int 
-idx1
+row
 , int 
-idx2
+col
 ,%0A  
@@ -428,22 +428,20 @@
     
-int sum, List%3C
+Map%3CString, 
 Inte
@@ -445,22 +445,20 @@
 nteger%3E 
-result
+memo
 ) %7B%0A    
@@ -465,97 +465,37 @@
     
-if (idx1 == 
+S
 tri
-a
 ng
-le.size()) %7B%0A            result.add(sum);%0A            return;%0A        %7D
+ key = row + %22%7C%22 + col;
 %0A   
@@ -507,14 +507,14 @@
 if (
-idx1 %3C
+row ==
  tri
@@ -521,24 +521,26 @@
 angle.size()
+-1
 ) %7B%0A        
@@ -547,18 +547,14 @@
     
-if (idx2 %3C
+return
  tri
@@ -559,39 +559,38 @@
 riangle.get(
-idx1).size()) %7B
+row).get(col);
 %0A           
@@ -582,32 +582,34 @@
 l);%0A        
+%7D%0A
         
 minimumTotal
@@ -600,105 +600,68 @@
     
-minimumTotal(triangle, idx1+1, idx2,%0A                    triangle.get(idx1).get(idx2)+sum, result
+if (memo.containsKey(key)) %7B%0A            return memo.get(key
 );%0A 
@@ -662,35 +662,64 @@
 ey);%0A       
+ %7D%0A
      
-%7D%0A
    
- 
+int min = Integer.MAX_VALUE;%0A
         if (
@@ -718,22 +718,19 @@
     if (
-idx2+1
+row
  %3C trian
@@ -733,26 +733,16 @@
 riangle.
-get(idx1).
 size()) 
@@ -755,19 +755,26 @@
         
- 
-  
+int min1 =
  minimum
@@ -793,733 +793,223 @@
 le, 
-idx1+1, idx2+1,%0A                    triangle.get(idx1).get(idx2+1)+sum, result);%0A            %7D%0A        %7D%0A    %7D%0A    %0A    public static void
+row+1, col, memo);%0A            int min2 =
  m
-a
 in
-(String%5B%5D args) %7B%0A        Problem120 prob = new Problem120();%0A        List%3CList%3CInteger%3E%3E triangle = new ArrayList%3C%3E();%0A        triangle.add(Arrays.asList(2));%0A        triangle.add(Arrays.asList(3, 4));%0A        triangle.add(Arrays.asList(6, 5, 7));%0A        triangle.add(Arrays.asList(4, 1, 8, -3));%0A        System.out.println(prob.minimumTotal(triangle));%0A%0A        triangle = new ArrayList%3C%3E();%0A        triangle.add(Arrays.asList(-1));%0A        triangle.add(Arrays.asList(2, 3));%0A        triangle.add(Arrays.asList(1, -1, -3));%0A        System.out.println(prob.minimumTotal(triangle))
+imumTotal(triangle, row+1, col+1, memo);%0A            min = Math.min(min1, min2) + triangle.get(row).get(col);%0A            memo.put(key, min);%0A        %7D%0A        return min
 ;%0A  

Solve problem 120 (finally!)