@@ -0,0 +1,1265 @@
+package dtprogrammer.github.io.p120;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.List;%0A%0A/**%0A * Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on%0A * the row below.%0A * %3Cp%3E%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 * %3Cp%3E%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%0A * the triangle.%0A * %3Cp%3E%0A * Time complexity: O (m * n)%0A * Space complexity: O (n)%0A */%0Apublic class Solution %7B%0A    public int minimumTotal(List%3CList%3CInteger%3E%3E triangle) %7B%0A        if (triangle == null) %7B%0A            return Integer.MAX_VALUE;%0A        %7D%0A        if (triangle.size() == 1) %7B%0A            return triangle.get(0).get(0);%0A        %7D%0A%0A        List%3CInteger%3E memo = new ArrayList%3C%3E(triangle.get(triangle.size() - 1));%0A        System.out.println(memo);%0A%0A%0A        for (int i = triangle.size() - 2; i %3E= 0; i--) %7B%0A            for (int j = 0; j %3C triangle.get(i).size(); j++) %7B%0A                memo.set(j, (triangle.get(i).get(j) + Math.min(memo.get(j), memo.get(j + 1))));%0A            %7D%0A        %7D%0A        return memo.get(0);%0A    %7D%0A%7D%0A

120. Triangle