@@ -0,0 +1,1743 @@
+// DP solution,%0A// modified version of https://discuss.leetcode.com/topic/1669/dp-solution-for-triangle%0Apublic class Solution %7B%0A  public int minimumTotal(List%3CList%3CInteger%3E%3E triangle) %7B%0A    int size = triangle.size();%0A    int%5B%5D dp = new int%5Bsize + 1%5D;%0A    for (int layer = size - 1; layer %3E= 0; layer--) %7B%0A      for (int i = 0; i %3C= layer; i++) %7B%0A        dp%5Bi%5D = Math.min(dp%5Bi%5D, dp%5Bi + 1%5D) + triangle.get(layer).get(i);%0A      %7D%0A    %7D%0A    return dp%5B0%5D;%0A  %7D%0A%7D%0A%0A// Recursive solution%0Apublic class Solution %7B%0A  public int minimumTotal(List%3CList%3CInteger%3E%3E triangle) %7B%0A    return minTotal(triangle, 0, 0);%0A  %7D%0A%0A  private int minTotal(List%3CList%3CInteger%3E%3E triangle, int depth, int i) %7B%0A    if (depth %3E= triangle.size()) return 0;%0A    if (depth == triangle.size() - 1) return triangle.get(depth).get(i);%0A    int left = minTotal(triangle, depth + 1, i);%0A    int right = minTotal(triangle, depth + 1, i + 1);%0A    return triangle.get(depth).get(i) + Math.min(left, right);%0A  %7D%0A%7D%0A%0A%0A// Recursive solution with memoization%0Apublic class Solution %7B%0A  public int minimumTotal(List%3CList%3CInteger%3E%3E triangle) %7B%0A    HashMap%3CString, Integer%3E memo = new HashMap%3CString, Integer%3E();%0A    return minTotal(triangle, 0, 0, memo);%0A  %7D%0A%0A  private int minTotal(List%3CList%3CInteger%3E%3E triangle, int depth, int i, HashMap%3CString, Integer%3E memo) %7B%0A    if (memo.containsKey(depth + %22-%22 + i)) return memo.get(depth + %22-%22 + i);%0A    if (depth %3E= triangle.size()) return 0;%0A    if (depth == triangle.size() - 1) return triangle.get(depth).get(i);%0A    int left = minTotal(triangle, depth + 1, i, memo);%0A    int right = minTotal(triangle, depth + 1, i + 1, memo);%0A    int sum = triangle.get(depth).get(i) + Math.min(left, right);%0A    memo.put(depth + %22-%22 + i, sum);%0A    return sum;%0A  %7D%0A%7D%0A

add triangle solution