@@ -0,0 +1,1476 @@
+package problems;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.Arrays;%0Aimport java.util.List;%0A%0A/* %0A * Given a triangle, find the minimum path sum from top to bottom. %0A * Each step you may move to adjacent numbers on the row below.%0A%0AFor example, given the following triangle%0A%5B%0A     %5B2%5D,%0A    %5B3,4%5D,%0A   %5B6,5,7%5D,%0A  %5B4,1,8,3%5D%0A%5D%0AThe minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).%0A%0ANote:%0ABonus point if you are able to do this using only O(n) extra space, %0Awhere n is the total number of rows in the triangle.%0A */%0A%0Apublic class Triangle %7B%0A    public int minimumTotal(List%3CList%3CInteger%3E%3E triangle) %7B%0A        int k = triangle.size();%0A        int%5B%5D A = new int%5Bk%5D; // dynamic storage%0A%0A        // bottom up%0A        for (int i = 0; i %3C k; i++)%0A            A%5Bi%5D = triangle.get(k - 1).get(i);%0A%0A        for (int i = k - 1; i %3E 0; i--) %7B%0A            for (int j = 0; j %3C i; j++)%0A                A%5Bj%5D = Math.min(A%5Bj%5D, A%5Bj + 1%5D) + triangle.get(i - 1).get(j);%0A        %7D%0A        return A%5B0%5D;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Triangle triangle = new Triangle();%0A%0A        List%3CList%3CInteger%3E%3E tri = new ArrayList%3CList%3CInteger%3E%3E();%0A        tri.add(new ArrayList%3CInteger%3E(Arrays.asList(2)));%0A        tri.add(new ArrayList%3CInteger%3E(Arrays.asList(3, 4)));%0A        tri.add(new ArrayList%3CInteger%3E(Arrays.asList(6, 5, 7)));%0A        tri.add(new ArrayList%3CInteger%3E(Arrays.asList(4, 1, 8, 3)));%0A%0A        System.out.println(triangle.minimumTotal(tri));%0A    %7D%0A%7D

Add Triangle