Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Notes:

1. Traverse from top to bottom: f[i][j] = Math.min(f[i-1][j], f[i-1][j-1]) + triangle[i][j];
2. Traverse from bottom to top, could use rolling array to save space: f[j] = Math.min(f[j], f[j+1]) + + triangle[i][j]. No overlap between two computations, so could use rolling array.
3. The initialize and answer are different for these two methods
4. Divide and conquer + memorized search: search(i, j) = Math.min(search(i+1, j), search(i+1, j+1)) + triangle[i][j].

    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null) {
            return -1;
        }

        int n = triangle.size();

        // state
        int[][] f = new int[n][n];

        // initialize
        f[0][0] = triangle.get(0).get(0);

        // function
        for (int i = 1; i < n; i++) {
            f[i][0] = f[i-1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; j++) {
                f[i][j] = Math.min(f[i-1][j], f[i-1][j-1]) + triangle.get(i).get(j);
            }
            f[i][i] = f[i-1][i-1] + triangle.get(i).get(i);
        }

        int sum = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            sum = Math.min(sum, f[n-1][i]);
        }

        // answer
        return sum;
    }

public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null) {
            return -1;
        }

        int n = triangle.size();

        // state
        int[] f = new int[n];

        // initialize
        for(int i = 0; i < n; ++i) {
            f[i] = triangle.get(n-1).get(i);
        }

        // function
        for (int i = n-2; i >= 0; --i) {
            for (int j = 0; j <= i; j++) {
                f[j] = Math.min(f[j], f[j+1]) + triangle.get(i).get(j);
            }
        }

        // answer
        return f[0];
    }

    private int search(int[][] triangle, int[][] minSum, int x, int y) {
        int n = triangle.length;
        if (x >= n) {
            return 0;
        }

        if (minSum[x][y] != Integer.MAX_VALUE) {
            return minSum[x][y];
        }

        minSum[x][y] = Math.min(search(x + 1, y), search(x + 1, y + 1))
            + triangle[x][y];
        return minSum[x][y];
    }

    public int minimumTotal(int[][] triangle) {
        if (triangle == null || triangle.length == 0) {
            return -1;
        }
        if (triangle[0] == null || triangle[0].length == 0) {
            return -1;
        }

        this.n = triangle.length;
        this.triangle = triangle;
        this.minSum = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                minSum[i][j] = Integer.MAX_VALUE;
            }
        }

        return search(0, 0);
    }