http://oj.leetcode.com/problems/triangle/

The problem statement is deceptive by mentioning path from “top” to “bottom”. I was fooled at first and tried to compare all the ways from the top to the bottoms. However, it is impractical since there are O(2^(n-1)) such paths.

I think this is a typical demonstration of the difference between bottom-up and top-down dynamic programming. It would be remarkably easier if we start from bottom and do upward. The solution is very short when the idea is set.

class Solution{
public:
int minimumTotal(vector<vector<int>>& triangle ){
int N = triangle.size();
if(!N)
return 0;
vector<int> r = triangle[N-1];
for(int i= N-2; i>=0; i--){
for(int j=0; j<=i; j++){
r[j] = triangle[i][j]+min(r[j],r[j+1]);
}
}
return r[0];
}
};

### Like this:

Like Loading...

*Related*