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.
像树这样的数据结构，直觉肯定是递归，几行就搞定。可惜TLE。不过程序应该是正确的。
class Solution { public: int min(int a, int b) { return a<b?a:b; } int sum(vector<vector<int> > &triangle, int index, int level) { if(level == triangle.size()-1) return triangle[level][index]; else return triangle[level][index] + min(sum(triangle, index, level+1), sum(triangle, index+1, level+1)); } int minimumTotal(vector<vector<int> > &triangle) { if(triangle.empty()) return 0; else return sum(triangle, 0, 0); } };
改进过程：
其实这类尾递归转换为迭代方式很简单，就是把结果传递下去，而不是通过return返回上来。
稍微改一下就行，核心思想是，每个元素存放从root到当前元素的最小和。
等计算完最后一行，遍历一遍找出最小的元素即可。
class Solution { public: int min(int a, int b) { return a<b?a:b; } int minimumTotal(vector<vector<int> > &triangle) { if(triangle.size() == 0) return 0; else if(triangle.size() == 1) return triangle[0][0]; else { for(vector<vector<int> >::size_type st1 = 1; st1 < triangle.size(); st1 ++) { for(vector<int>::size_type st2 = 0; st2 < triangle[st1].size(); st2 ++) { if(st2 == 0) triangle[st1][st2] = triangle[st1][st2] + triangle[st1-1][st2]; else if(st2 == triangle[st1].size()-1) triangle[st1][st2] = triangle[st1][st2] + triangle[st1-1][st2-1]; else triangle[st1][st2] = triangle[st1][st2] + min(triangle[st1-1][st2], triangle[st1-1][st2-1]); } } int size = triangle.size(); int result = triangle[size-1][0]; for(vector<int>::size_type st = 1; st < triangle[size-1].size(); st ++) if(triangle[size-1][st] < result) result = triangle[size-1][st]; return result; } } };
上述是使用top-down方法。看了一下Discussion发现其实可以简化一下，去掉最后一次遍历过程，使用bottom-up方法将最小值汇聚到root
class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { if(triangle.size() == 0) return 0; for(vector<vector<int> >::size_type st1 = triangle.size()-1; st1 > 0; st1 --) { for(vector<int>::size_type st2 = 0; st2 < triangle[st1].size()-1; st2 ++) { if(triangle[st1][st2] < triangle[st1][st2+1]) triangle[st1-1][st2] += triangle[st1][st2]; else triangle[st1-1][st2] += triangle[st1][st2+1]; } } return triangle[0][0]; } };
以上都是in-place的做法。
但是按照题意O(n)空间复杂度，其实可以用类似的方法将中间结果保存在开辟的空间中，不改变输入数据。
【LeetCode】Triangle,布布扣,bubuko.com
原文：http://www.cnblogs.com/ganganloveu/p/3724450.html