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 is11(i.e.,2+3+5+1= 11).

Note:

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.

Analysis

DP vs DFS / BFS

此问题乍一看很像Tree， 因此容易想到DFS或者BFS的方案，加上记忆化搜索，可以勉强AC。但是仔细观察，相邻节点总是会有共用的分支，也就是说有重叠的子问题 overlapping subproblems，而且状态转移方程很容易得到：

O(1) 时间复杂度的递推关系 minpath[k][i] = min( minpath[k+1][i], minpath[k+1][i+1]) + triangle[k][i];

其中minpath[k][i]表示第k行，第i列的元素到bottom的最小路径和, 即min path sum

也可以说有一个最优子结构 optimal substructure。这样的情况下DP可能有最佳的时间复杂度。

Top-Down vs Bottom-Up

LeetCode论坛分析 @stellari：

• For 'top-down' DP, starting from the node on the very top, we recursively find the minimum path sum of each node. When a path sum is calculated, we store it in an array (memoization); the next time we need to calculate the path sum of the same node, just retrieve it from the array. O(N^2) space.

• 'Bottom-up' DP, on the other hand, is very straightforward: we start from the nodes on the bottom row; the min pathsums for these nodes are the values of the nodes themselves. From there, the min pathsum at the ith node on the kth row would be the lesser of the pathsums of its two children plus the value of itself.

空间优化小Trick：

Or even better, since the row minpath[k+1] would be useless after minpath[k] is computed, we can simply set minpath as a 1D array, and iteratively update itself:

For the kth level:
minpath[i] = min( minpath[i], minpath[i+1]) + triangle[k][i];

因为每一行的结果在下一行用过之后就不会被用到，可以将计算结果直接存入自身，也就节约了一个维度的空间。O(n).

此外也可以用triangle本身存储中间结果，那么space就变成O(1)，参考：My 8 line DP Java code(4 meaningful lines) with O(1) space:

triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)));

下标优化小Trick：

声明DP数组时，多加一位：int[] minpath = new int[size + 1];

这样就可以直接从Bottom那一行开始运用递推关系，而不用从先复制最后一行赋值给DP数组，再从倒数第二行开始用递推关系。

Solution

DP Buttom Up 1D array (4ms 90.59% AC)

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int size = triangle.size();

        int[] minpath = new int[size];
        int k = 0;
        for (Integer e : triangle.get(size - 1)) {
            minpath[k++] = e;
        }
        for (int row = size - 2; row >= 0; row--) {
            for (int i = 0; i <= row; i++) {
                minpath[i] = Math.min(minpath[i], minpath[i + 1]) + triangle.get(row).get(i);
            }
        }
        return minpath[0];
    }
}

*DP - Bottom Up - Improved implementation with size = N + 1 array (4ms 90.59% AC)

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int size = triangle.size();

        int[] minpath = new int[size + 1];
        for (int row = size - 1; row >= 0; row--) {
            for (int i = 0; i <= row; i++) {
                minpath[i] = Math.min(minpath[i], minpath[i + 1]) + triangle.get(row).get(i);
            }
        }
        return minpath[0];
    }
}

DP with O(1) space

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        for(int i = triangle.size() - 2; i >= 0; i--)
            for(int j = 0; j <= i; j++)
                triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)));
        return triangle.get(0).get(0);
    }
}

Top Down DP with memorization - DFS (102 ms 1.05% AC)

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0 || triangle.get(0).size() == 0) return 0;
        return minPathSumHelper(triangle, new HashMap<String, Integer>(), new Coordinate(0, 0));
    }
    public int minPathSumHelper(List<List<Integer>> triangle, HashMap<String, Integer> map, Coordinate cor) {
        String key = cor.row + "," + cor.col;
        if (map.containsKey(key)) {
            return map.get(key);   
        }
        if (cor.row >= triangle.size() || cor.col >= triangle.get(triangle.size() - 1).size()) return 0;
        int val = triangle.get(cor.row).get(cor.col);
        int min = val + 
            Math.min(minPathSumHelper(triangle, map, new Coordinate(cor.row + 1, cor.col)), 
                     minPathSumHelper(triangle, map, new Coordinate(cor.row + 1, cor.col + 1)));
        map.put(key, min);
        return min;
    }

    class Coordinate {
        int row, col;
        Coordinate (int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

Reference

https://leetcode.com/problems/triangle/discuss/38730/DP-Solution-for-Triangle