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
Copy [
[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
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:
Copy For the kth level:
minpath[i] = min( minpath[i], minpath[i+1]) + triangle[k][i]; 因为每一行的结果在下一行用过之后就不会被用到，可以将计算结果直接存入自身，也就节约了一个维度的空间。O(n).
Copy 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)
Copy 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)
Copy 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
Copy 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)
Copy 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