简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career
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.
» Solve this problemBonus 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.
It cost some of my time to think about it. After search it online, I got the key point is DP and we can replace the value in triangle, so that we can do it in place.
The algorithm is easy.
Do it bottom up, sum up the smaller elements that the current one can reach in next level. Return the first node in first level in the end.
I think the variable "col" should be named "row" to be more understandable.
ReplyDeleteI wrote in a recursive way, but is says that I exceed time limit, do you know why?
ReplyDeleteint minimumTotal(vector > &triangle) {
return minimumTotalDFS(triangle, 0, 0);
}
int minimumTotalDFS(vector > &triangle, int lvl, int idx){
if(lvl >= triangle.size() - 1)
return triangle[lvl][idx];
int leftMin = minimumTotalDFS(triangle, lvl + 1, idx);
int rightMin = minimumTotalDFS(triangle, lvl + 1, idx + 1);
return triangle[lvl][idx] + min(leftMin, rightMin);
}