Triangle [source code]
public class Triangle {
static
/******************************************************************************/
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle.size () == 0)
return 0;
int N = triangle.size ();
int[] memo = new int[N], nmemo = new int[N];
for (int i = 0; i < N; i++)
memo[i] = triangle.get (N - 1).get (i);
for (int i = N - 2; i >= 0; i--) {
for (int j = 0; j < N - (N - 1 - i); j++)
nmemo[j] = Math.min (memo[j], memo[j + 1]) + triangle.get (i).get (j);
memo = nmemo;
}
return memo[0];
}
}
/******************************************************************************/
public static void main(String[] args) {
Triangle.Solution tester = new Triangle.Solution();
}
}
感觉就是一个直白的DP问题, 最后这个Follow-Up其实也就是一个DP空间优化的小技巧; 思路感觉有就赶紧开始写, 毕竟有些题目写起来的麻烦程度不低于思路;
比较轻松的秒杀了, 速度是8ms (51%);
上面j的循环范围的计算比较蠢, 实际上就是i + 1就行了;
没有editorial;
https://leetcode.com/problems/triangle/discuss/38730/DP-Solution-for-Triangle
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 are overlapping 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 is optimal 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];Thus, we have the following solution
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];
}
这里发现, 实际上nmemo这个辅助的array都是不需要的, 因为当你把i位置更新完了之后, 之前的那个i就不需要了(右边的全都不需要memo[i]了), 所以这个时候直接写进去就行了; 虽然你在计算nmemo[i]的时候用到了memo[i+1], 但是你并没有write他, 还是正常的, 所以你自己在[i]位置完成你自己的更新, 不会影响[i+1]位置的情况;
另外, 解决空间限制的另外一个办法就是modify input:
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);
}
I struggled the shit out to get the top down solution working and then realized how beautiful the bottom up solution is. Life lesson : Some times you have a step away from the problem and look at it from a different perspective to actually solve it :)
If someone is curious to look at the top-down approach code:
public int MinimumTotal(IList<IList<int>> triangle)
{
if (triangle.Count == 0)
{
return 0;
}
int[] minSum = new int[triangle.Count];
int minTotal = 0;
for (int i = 0; i < triangle.Count; i++)
{
IList<int> curr = triangle[i];
if (i == 0)
{
minSum[0] = curr[0];
minTotal = curr[0];
continue;
}
int prev = int.MaxValue;
minTotal = int.MaxValue;
for (int j = 0; j < curr.Count; j++ )
{
int temp = minSum[j];
minSum[j] = j == curr.Count - 1 ? prev + curr[j] : curr[j] + Math.Min(prev, minSum[j]);
prev = temp;
minTotal = Math.Min(minTotal, minSum[j]);
}
}
return minTotal;
}
意思是这题幸亏没有踩到Top-Down的坑; 大概看了一下他这个算法, 感觉就是一个从上到下穷搜的过程, 注意维护一个parent的概念;
modifying input makes it thread unsafe. You’d better keep that until interviewer ask for it,
反对modify input的一个重要理由, 以前见到过的;
it’s O(n), if it’s linked list, I think we should better use iterator to traverse every layer, otherwise using get/set the time complexity would be terrible
为什么iterator就可以避免这个问题?
submission:5(99):
class Solution {
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);
}
}
大概看了一下, 就是上面那个Top-Down的做法, 因为利用了recursion所以很快? 不然不知道为什么了, 毕竟他这里也是直接对list进行操作的, 所以不可能是这个的原因;
大概的核心思路还是类似的, 从上到下的时候, 站在一个当前的DP的位置, 你要向上lookup, 看看你可以利用上一层的哪些源头;
另外, 如果真的要用recursion, 还要重新理解一下为什么这里仍然是O(N)的space: recursion Stack最多是N层的高度;
Problem Description
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).
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.
Difficulty:Medium
Total Accepted:126.8K
Total Submissions:364.9K
Contributor:LeetCode
Related Topics
arraydynamic programming