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).
https://www.cnblogs.com/struggleli/p/6934287.html
X. Bottom up
https://leetcode.com/problems/triangle/discuss/38724/7-lines-neat-Java-Solution
X. Bottom up
https://leetcode.com/problems/triangle/discuss/38724/7-lines-neat-Java-Solution
public int minimumTotal(List<List<Integer>> triangle) {
int[] A = new int[triangle.size()+1];
for(int i=triangle.size()-1;i>=0;i--){
for(int j=0;j<triangle.get(i).size();j++){
A[j] = Math.min(A[j],A[j+1])+triangle.get(i).get(j);
}
}
return A[0];
}
DP:
This problem is quite well-formed in my opinion. The triangle has a tree-like structure, which would lead people to think about traversal algorithms such as DFS. However, if you look closely, you would notice that the adjacent nodes always share a 'branch'. In other word, there areoverlapping subproblems. Also, suppose x and y are 'children' of k. Once minimum paths from x and y to the bottom are known, the minimum path starting from k can be decided in O(1), that isoptimal substructure. Therefore, dynamic programming would be the best solution to this problem in terms of time complexity.
What I like about this problem even more is that the difference between 'top-down' and 'bottom-up' DP can be 'literally' pictured in the input triangle. 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. However, you will need a cache that is at least the same size as the input triangle itself to store the pathsum, which takes O(N^2) space. With some clever thinking, it might be possible to release some of the memory that will never be used after a particular point, but the order of the nodes being processed is not straightforwardly seen in a recursive solution, so deciding which part of the cache to discard can be a hard job.
'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, i.e.:
minpath[k][i] = min( minpath[k+1][i], minpath[k+1][i+1]) + triangle[k][i];
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];
int minimumTotal(vector<vector<int> > &triangle) { int n = triangle.size(); vector<int> minlen(triangle.back()); for (int layer = n-2; layer >= 0; layer--) // For each layer { for (int i = 0; i <= layer; i++) // Check its every 'node' { // Find the lesser of its two children, and sum the current value in the triangle with it. minlen[i] = min(minlen[i], minlen[i+1]) + triangle[layer][i]; } } return minlen[0]; }
O(1) space:
modifying input makes it thread unsafe. You'd better keep that until interviewer ask for it,
A similar solution in java but without using additional memory. Just save the value in the triangle itself.
public int minimumTotal(List<List<Integer>> triangle) { if(triangle.size() == 0) return 0; for (int i=triangle.size() - 2; i>=0; i--) { for (int j=0; j<=i; j++) { List<Integer> nextRow = triangle.get(i+1); int sum = Math.min(nextRow.get(j), nextRow.get(j+1)) + triangle.get(i).get(j); triangle.get(i).set(j, sum); } } return triangle.get(0).get(0); }
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle.size() == 0)
return 0;
if (triangle.size() == 1)
return triangle.get(0).get(0);
int[] dp = new int[triangle.size()];
dp[0] = triangle.get(0).get(0);
return minimumTotal(triangle, dp, 1);
}
public int minimumTotal(List<List<Integer>> triangle, int[] dp, int lvlidx) {
/**
* dp: dp[i]_lvlidx = the min path sum up to current level and up to
* index i
*
* dp[0]_lvlidx = this_level_list[0] + dp[0]_(lvlidx-1);
* dp[end]_lvlidx = this_level_list[end] + dp[end-1]_(lvlidx-1);
*
* dp[i]_lvlidx = this_level_list[i] + min{ dp[i-1]_(lvlidx-1),
* dp[i]_(lvlidx-1) };
*/
List<Integer> list = triangle.get(lvlidx);
int pre = dp[0], temp;
dp[0] += list.get(0);
for (int i = 1; i < lvlidx; i++) {
temp = dp[i];
dp[i] = list.get(i) + Math.min(pre, dp[i]);
pre = temp;
}
dp[lvlidx] = pre + list.get(lvlidx);
if (lvlidx + 1 == triangle.size()) {
int res = dp[0];
for (int i = 1; i <= lvlidx; i++)
res = Math.min(res, dp[i]);
return res;
}
return minimumTotal(triangle, dp, lvlidx + 1);
}
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);
}
}
The idea is simple.
1) Go from bottom to top.
2) We start form the row above the bottom row [size()-2].
3) Each number add the smaller number of two numbers that below it.
4) And finally we get to the top we the smallest sum.
What if the List is LinkedList? What is the complexity of the get function ?
Top Down - BFS, DP
http://yucoding.blogspot.com/2013/04/leetcode-question-112-triangle.html
https://leetcode.com/discuss/51099/java-top-down-dp-solution-no-extra-space
public int minimumTotal(List<List<Integer>> triangle) { List<Integer> prev = triangle.get(0); int min = prev.get(0); for (int i = 1; i < triangle.size(); i++) { List<Integer> cur = triangle.get(i); min = Integer.MAX_VALUE; for(int j = 0; j < cur.size(); j++) { int minSum = cur.get(j) + getPreviousMin(j, prev); cur.set(j,minSum); if(minSum < min) min = minSum; } prev = cur; } return min; } private int getPreviousMin(int j, List<Integer> prev) { int m1 = (j>=prev.size())?Integer.MAX_VALUE : prev.get(j); int m2 = (j<=0)? Integer.MAX_VALUE : prev.get(j-1); return Math.min(m1, m2); }
http://www.cnblogs.com/yuzhangcmu/p/4147764.html
int minimumTotal(vector<vector<int> > &triangle) { int n = triangle.size(); if (n==0){return 0;} for (int i=1;i<n;i++){ for (int j=0;j<triangle[i].size();j++){ if (j==0){triangle[i][j] += triangle[i-1][j];} if (j>0){ if (i>j){ triangle[i][j] += min(triangle[i-1][j-1],triangle[i-1][j]); }else{ triangle[i][j] += triangle[i-1][j-1]; } } } } sort(triangle[n-1].begin(),triangle[n-1].end()); //get min return triangle[n-1][0]; }https://leetcode.com/discuss/51099/java-top-down-dp-solution-no-extra-space
public int minimumTotal(List<List<Integer>> triangle) { List<Integer> prev = triangle.get(0); int min = prev.get(0); for (int i = 1; i < triangle.size(); i++) { List<Integer> cur = triangle.get(i); min = Integer.MAX_VALUE; for(int j = 0; j < cur.size(); j++) { int minSum = cur.get(j) + getPreviousMin(j, prev); cur.set(j,minSum); if(minSum < min) min = minSum; } prev = cur; } return min; } private int getPreviousMin(int j, List<Integer> prev) { int m1 = (j>=prev.size())?Integer.MAX_VALUE : prev.get(j); int m2 = (j<=0)? Integer.MAX_VALUE : prev.get(j-1); return Math.min(m1, m2); }
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size(), value1, value2;
for(int i = 1; i < n; i++){
for(int j = 0; j <= i; j++){
if(j == 0){
value1 = triangle.get(i - 1).get(0);
}else{
value1 = j == i ? triangle.get(i - 1).get(j - 1) : Math.min(triangle.get(i - 1).get(j - 1), triangle.get(i - 1).get(j));
}
value2 = triangle.get(i).get(j);
triangle.get(i).set(j, value1 + value2);
}
}
int min = Integer.MAX_VALUE;
for(int k = 0; k < n; k++){ // we can keep track of min in the above for-for loop
min = Math.min(min, triangle.get(n - 1).get(k));
}
return min;
}
Solution - DFS, Recursion
Solution - DFS, Recursion
This algorithm actually expand the triangle into a full binary tree and check each node constant times. For example, the example triangle becomes
[
[2],
[3 , 4],
[6 , 5 5 , 7],
[4,1 1,8 1,8 8,3]
]
Given a triangle of n rows, the resulted binary tree will have O(2^n) nodes. Thus, it takes O(2^n) time, where n is the total number of rows, and O(n) spaces for DFS.
Since numbers could be negative, we cannot prune sub-triangle when the current sum is no less than current minimum sum.
private int DFS(ArrayList<ArrayList<Integer>> triangle, int row, int column, int sum, int minSum) {
// add itself
sum += triangle.get(row).get(column);
if (row == triangle.size() - 1) { // last row
if (sum < minSum) return sum;
} else {
minSum = DFS(triangle, row+1, column, sum, minSum);
minSum = DFS(triangle, row+1, column+1, sum, minSum);
}
return minSum;
}
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
return DFS(triangle, 0, 0, 0, Integer.MAX_VALUE);
}
使用DFS 加记忆矩阵的解法.
4 public int minimumTotal1(List<List<Integer>> triangle) { 5 if (triangle == null || triangle.size() == 0) { 6 return 0; 7 } 9 int rows = triangle.size(); 10 int[][] mem = new int[rows][rows]; 11 for (int i = 0; i < rows; i++) { 12 for (int j = 0; j < rows; j++) { 13 mem[i][j] = Integer.MAX_VALUE; 14 } 15 } 17 return dfs(triangle, 0, 0, mem); 18 } 19 20 public int dfs(List<List<Integer>> triangle, int row, int col, int[][] mem) { 21 if (mem[row][col] != Integer.MAX_VALUE) { 22 return mem[row][col]; 23 } 24 25 if (row == triangle.size() - 1) { 26 mem[row][col] = triangle.get(row).get(col); 27 } else { 28 int left = dfs(triangle, row + 1, col, mem); 29 int right = dfs(triangle, row + 1, col + 1, mem); 30 mem[row][col] = triangle.get(row).get(col) + Math.min(left, right); 31 } 32 33 return mem[row][col]; 34 }
Solution - DFS, DP
Notice that in the above solution, we revisit each number multiple times which may not be necessary. For example, the sums in the small triangle
That hints us to use DP to optimize the algorithm.
Instead of recalculate all the time, we store the known minimun sum from the current node to bottom in a table. Then next time when we hit the same number, it only takes O(1) time to loop up the value.
Bottom-Up (Good Solution)
http://www.programcreek.com/2013/01/leetcode-triangle-java/
We can actually start from the bottom of the triangle.
http://www.zrzahid.com/min-sum-path-in-triangle/
Notice that in the above solution, we revisit each number multiple times which may not be necessary. For example, the sums in the small triangle
[ [5] [1,8] ]has been recalculated along the path via number 3 and 4.
That hints us to use DP to optimize the algorithm.
Instead of recalculate all the time, we store the known minimun sum from the current node to bottom in a table. Then next time when we hit the same number, it only takes O(1) time to loop up the value.
private int DFS(ArrayList<ArrayList<Integer>> triangle, int row, int column,
HashMap<Integer, Integer> rowMin) {
int min = triangle.get(row).get(column);
if (row == triangle.size() - 1) { // last row, return itself
return min;
}
if (!rowMin.containsKey(row+1)) { // calculate for first column
min += Math.min(DFS(triangle, row+1, column, rowMin),
DFS(triangle, row+1, column+1, rowMin));
} else {
min += Math.min(rowMin.get(row+1),
DFS(triangle, row+1, column+1, rowMin));
}
rowMin.put(row, min);
return min;
}
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
return DFS(triangle, 0, 0, new HashMap<Integer, Integer>());
} Bottom-Up (Good Solution)
http://www.programcreek.com/2013/01/leetcode-triangle-java/
We can actually start from the bottom of the triangle.
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) { int[] total = new int[triangle.size()]; int l = triangle.size() - 1; for (int i = 0; i < triangle.get(l).size(); i++) { total[i] = triangle.get(l).get(i); } // iterate from last second row for (int i = triangle.size() - 2; i >= 0; i--) { for (int j = 0; j < triangle.get(i + 1).size() - 1; j++) { total[j] = triangle.get(i).get(j) + Math.min(total[j], total[j + 1]); } } return total[0]; } |
int minimumTotal(vector<vector<int> > &triangle) { int triangleSize = triangle.size(); if(triangleSize == 0){ return 0; } vector<int> saveMinDistance(triangle[triangleSize - 1].size() + 1, 0); int first,second,current; first = second = current = 0; for(int i = triangleSize - 1; i >=0; i--){ for(int j = 0; j < i + 1; j++){ current = triangle[i][j]; first = current + saveMinDistance[j]; second = current + saveMinDistance[j + 1]; saveMinDistance[j] = first < second ? first : second; } } return saveMinDistance[0];}http://www.zrzahid.com/min-sum-path-in-triangle/
Notice that if we start from top and do a topdown dp then we might get wrong result as in example 2 it will return 15 = [2, 4, 5, 4]. But the actual minimum path is 13 = [2, 5, 5, 1]. That is we need to do a bottom-up computation for the dp. That is,
dp[level][i] = triangle[level][i] + min{dp[level+1][i], dp[level+1][i+1]}
//O(n^2) time and O(n^2) space for dp table public static int triangleMinSumPath(List<int[]> triangle){ int levels = triangle.size(); int dp[][] = new int[levels][levels]; dp[levels-1] = triangle.get(levels-1); //bottom up Dijkstra for(int l = levels-2; l>=0 ; l--){ for(int i = 0; i<=l; i++){ dp[l][i] = Math.min(dp[l+1][i], dp[l+1][i+1]) + triangle.get(l)[i]; } } return dp[0][0]; }
O(n) space solution
If we print the dp table of the above code for example 2 then we will see the following –
If we print the dp table of the above code for example 2 then we will see the following –
Triangle -
[2],
[5,4],
[5,5,7],
[1,4,8,3]
dp table -
13, 0, 0, 0
11, 13, 0, 0
6, 9, 10, 0
1, 4, 8, 3
If we look closely then we can see that the table has meaningful values in lower half only and at each level bottom up we have one of the column value getting fixed. So, we could have basically used the bottom level array as the dp table and at each level we update the columns bottom up. In this way we can decrease the space from O(n^2) to O(n). Below is the modified implementation of the above code by using O(n) space for dp table.
//O(n^2) time and O(n) space public static int triangleMinSumPath2(List<int[]> triangle){ int levels = triangle.size(); int dp[] = new int[levels]; dp = triangle.get(levels-1); //bottom up Dijkstra for(int l = levels-2; l>=0 ; l--){ for(int i = 0; i<=l; i++){ dp[i] = Math.min(dp[i], dp[i+1]) + triangle.get(l)[i]; } } return dp[0]; }Read full article from Leetcode Triangle solution | easycpp
