Triangle

At first glance, I thought it is recursion problem, since it is related to or similar with the "Tree" structure. So this time my code is like below:

 public class Solution {  
   public int minimumTotal(List<List<Integer>> triangle) {  
     if (triangle == null) return 0;  
     if (triangle.size() == 1) return triangle.get(0).get(0);  
     ArrayList<Integer> list = new ArrayList<Integer>();  
     WrapInt wi = new WrapInt(Integer.MAX_VALUE);  
     findMinSum(triangle, 0, 0, wi, list);  
     return wi.val;  
   }  
   public void findMinSum(List<List<Integer>> triangle, int level, int idx, WrapInt wi, ArrayList<Integer> list){  
     list.add(triangle.get(level).get(idx));  
     if (list.size() == triangle.size()){  
       int sum = 0;  
       for (int e : list){  
         sum += e;  
       }  
       if (sum < wi.val) wi.val = sum;  
       return;  
     }  
     findMinSum(triangle, level + 1, idx , wi, list);  
     list.remove(list.size() - 1);  
     findMinSum(triangle, level + 1, idx+1, wi, list);  
     list.remove(list.size() - 1);  
   }  
 }  
 class WrapInt{  
   int val;  
   public WrapInt(int v){  
     val = v;  
   }  
 }  

Apparently, this is not very efficient. It is like a brute force answer, with all possible results been computed. Time complexity should be O(2^(n - 1)). NO!! Too much time.

Now we can know that we must waste time in computing redundant path, or duplicate computing. To improve recursion version, DP is usually applied.

Thanks again for code ganker's good job.  Key point is sum[i][j](the "min sum value" at level i, index j) is equal to min(sum[i-1][j-1], sum[i-1][j]) + triangle[i][j]. This is a bottom-to-up idea. For each level, calculation is based on previous level. Overall, each element is traversed once, so time is O(n^2), and using an array can keep space O(n)

Hope I can think of this idea by myself next time.