Monday, November 24, 2014

[LeetCode] 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 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.

1. 对第j层 (j = 0 ~ n-1)，一共有j+1个数：0:j。而上一层有j个数：0:j-1
2. 除去头尾两个数外，curPath[i] = min(prePath[i-1], prePath[i]) + triangle[j][i]
3. 头尾的特殊情况：curPath[0] = prePath[0] + triangle[j][0]；curPath[j] = prePath[j-1] + triangle[j][j]
4. 在计算下一层前，需要交换curPath和prePath。
5. 在最后一层curPath计算结束后，在其中找一个最小值即为整个树的min path sum。

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24``` ```class Solution { public: int minimumTotal(vector > &triangle) { if(triangle.empty()) return 0; int n = triangle.size(); vector curPath(n,INT_MAX); vector prePath(n,INT_MAX); curPath[0] = triangle[0][0]; for(int lvl=1; lvl

1 comment:

1. 如果从底部开始计算，好像代码会简洁不少，当然也是用到了滚动数组

class Solution {
public:
int minimumTotal(vector>& triangle) {
if(triangle.size()<1) return 0;

vector tmp=triangle[triangle.size()-1];
for(int i=int(triangle.size())-2;i>=0;i--){
for(int j=0;j<triangle[i].size();j++){
tmp[j]=min(tmp[j],tmp[j+1])+triangle[i][j];
}
//tmp.pop_back();
}

return tmp[0];
}