@@ -0,0 +1,1500 @@
+/***%0A * Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.%0A *%0A * For 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%0A * The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).%0A *%0A * Note:%0A * Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.%0A */%0A%0A// Dynamic Programming:%0A// Function:%0A// f(i, j) = min%7Bf(i + 1, j), f(i + 1, j + 1)) + V(i, j)%0A//%0Aimport java.util.ArrayList;%0Apublic class Triangle %7B%0A    public int minimumTotal(ArrayList%3CArrayList%3CInteger%3E%3E triangle) %7B%0A        for (int i = triangle.size() - 2; i %3E= 0; i--) %7B%0A            System.out.printf(%22i %25d%5Cn%22, i);%0A            for (int j = triangle.get(i).size() - 1; j %3E= 0; j--) %7B%0A                triangle.get(i).set(j, Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)) + triangle.get(i).get(j));%0A                System.out.printf(%22i %25d, j %25d, val %25d%5Cn%22, i, j, triangle.get(i).get(j));%0A            %7D%0A        %7D%0A        return triangle.get(0).get(0);%0A    %7D%0A%0A    public static void main (String args%5B%5D) %7B%0A        Triangle tri = new Triangle();%0A        ArrayList%3CArrayList%3CInteger%3E%3E test = new ArrayList%3CArrayList%3CInteger%3E%3E();%0A        test.add(new ArrayList%3CInteger%3E()%7B%7Badd(1);%7D%7D);%0A        test.add(new ArrayList%3CInteger%3E()%7B%7Badd(2); add(3);%7D%7D);%0A        System.out.printf(%22%25d%5Cn%22, tri.minimumTotal(test));%0A    %7D%0A%7D%0A

add Triangle.java