Descripition
https://oj.leetcode.com/submissions/detail/13248579/
Difficutly: 2.0/5.0
Solution
It is much easier and faster to solve this problem following a bottom-up manner, which can be viewed as a tree DP problem.
class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
if (triangle.size() == 0)
return 0;
vector<int> minPathSum = triangle[triangle.size()-1];
for (int idxRow = triangle.size()-2; idxRow >= 0; -- idxRow)
for (int i = 0; i < idxRow+1; ++ i)
minPathSum[i] = min(minPathSum[i], minPathSum[i+1]) + triangle[idxRow][i];
return minPathSum[0];
}
};