Triangle

1package pkg5leetcode.interview150;2 3/*4 * Triangle | LC 1205 * APPROACH: Bottom-up DP min path sum using next row.6 * COMPLEXITY: Time O(n^2), Space O(n)7 */8public class interview150_LC120Triangle {9    static int minimumTotal(java.util.List<java.util.List<Integer>> triangle) {10        int n = triangle.size();11        int[] dp = new int[n];12        for (int i = 0; i < n; i++) dp[i] = triangle.get(n - 1).get(i);13        for (int r = n - 2; r >= 0; r--) {14            for (int c = 0; c <= r; c++)15                dp[c] = triangle.get(r).get(c) + Math.min(dp[c], dp[c + 1]);16        }17        return dp[0];18    }19 20    public static void main(String[] args) {21        java.util.List<java.util.List<Integer>> t = java.util.Arrays.asList(22            java.util.Arrays.asList(2),23            java.util.Arrays.asList(3, 4),24            java.util.Arrays.asList(6, 5, 7),25            java.util.Arrays.asList(4, 1, 8, 3));26        check(minimumTotal(t) == 11, "case1");27        check(minimumTotal(java.util.Arrays.asList(java.util.Arrays.asList(-10))) == -10, "case2");28        System.out.println("all tests passed");29    }30 31    static void check(boolean cond, String name) {32        if (!cond) throw new AssertionError("FAILED: " + name);33        System.out.println("  PASS " + name);34    }35}