// DP solution,
// modified version of https://discuss.leetcode.com/topic/1669/dp-solution-for-triangle
public class Solution {
  public int minimumTotal(List<List<Integer>> triangle) {
    int size = triangle.size();
    int[] dp = new int[size + 1];
    for (int layer = size - 1; layer >= 0; layer--) {
      for (int i = 0; i <= layer; i++) {
        dp[i] = Math.min(dp[i], dp[i + 1]) + triangle.get(layer).get(i);
      }
    }
    return dp[0];
  }
}

// Recursive solution
public class Solution {
  public int minimumTotal(List<List<Integer>> triangle) {
    return minTotal(triangle, 0, 0);
  }

  private int minTotal(List<List<Integer>> triangle, int depth, int i) {
    if (depth >= triangle.size()) return 0;
    if (depth == triangle.size() - 1) return triangle.get(depth).get(i);
    int left = minTotal(triangle, depth + 1, i);
    int right = minTotal(triangle, depth + 1, i + 1);
    return triangle.get(depth).get(i) + Math.min(left, right);
  }
}


// Recursive solution with memoization
public class Solution {
  public int minimumTotal(List<List<Integer>> triangle) {
    HashMap<String, Integer> memo = new HashMap<String, Integer>();
    return minTotal(triangle, 0, 0, memo);
  }

  private int minTotal(List<List<Integer>> triangle, int depth, int i, HashMap<String, Integer> memo) {
    if (memo.containsKey(depth + "-" + i)) return memo.get(depth + "-" + i);
    if (depth >= triangle.size()) return 0;
    if (depth == triangle.size() - 1) return triangle.get(depth).get(i);
    int left = minTotal(triangle, depth + 1, i, memo);
    int right = minTotal(triangle, depth + 1, i + 1, memo);
    int sum = triangle.get(depth).get(i) + Math.min(left, right);
    memo.put(depth + "-" + i, sum);
    return sum;
  }
}

@@ -452,16 +452,572 @@
 %0A  %7D%0A%7D%0A%0A
+// My DP solution (13.02.2018)%0A// Runs in O(N%5E2) time, where N is the number of levels and O(N) space.%0Aclass Solution %7B%0A  public int minimumTotal(List%3CList%3CInteger%3E%3E triangle) %7B%0A    if (triangle.size() == 0) return 0;%0A    int level = triangle.size() - 1; // the bottom level%0A    int%5B%5D curr = new int%5Btriangle.get(level).size() + 1%5D;%0A    for (int i = level; i %3E= 0; i--) %7B%0A      List%3CInteger%3E l = triangle.get(i);%0A      for (int j = 0; j %3C l.size(); j++) %7B%0A        curr%5Bj%5D = Math.min(curr%5Bj%5D, curr%5Bj+1%5D) + l.get(j);%0A      %7D%0A    %7D%0A    return curr%5B0%5D;%0A  %7D%0A%7D%0A%0A
 // Recur
@@ -2284,16 +2284,678 @@
 turn sum;%0A  %7D%0A%7D%0A
+%0A// Top down recursive solution%0Aclass Solution %7B%0A  public int minimumTotal(List%3CList%3CInteger%3E%3E triangle) %7B%0A    if (triangle.size() == 0) return 0;%0A    int%5B%5D res = new int%5B%5D %7B Integer.MAX_VALUE %7D;%0A    helper(triangle, 0, 0, 0, res);%0A    return res%5B0%5D;%0A  %7D%0A%0A  private void helper(List%3CList%3CInteger%3E%3E triangle, int level, int idx, int sum, int%5B%5D res) %7B%0A    if (triangle.size() == level + 1) %7B%0A      sum += triangle.get(level).get(idx);%0A      res%5B0%5D = Math.min(res%5B0%5D, sum);%0A    %7D else %7B%0A      helper(triangle, level + 1, idx, sum + triangle.get(level).get(idx), res);%0A      helper(triangle, level + 1, idx + 1, sum + triangle.get(level).get(idx), res);%0A    %7D%0A  %7D%0A%7D%0A

update solution