原题：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.
相似修改：Number Triangle
Time limit: 1 second Memory limit: 64MB
Problem Description
Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.
Input Description
There are multiple test cases. The first line of each test case contains R (1 <= R <= 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle. All the supplied integers are non-negative and no larger than 100.
Output Description
Print a single line containing the largest sum using the traversal specified for each test case.
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
下面给出原题的解法：
解法一：从上往下遍历,时间复杂度为O(n^2),且需要处理每行的头和尾
class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
vector<vector<int>> temp(triangle);
vector<vector<int>>::size_type length=temp.size();
int i,j;
for(i=;i<length;i++){
vector<int>::size_type length_inner = temp[i].size();
for(j=;j<length_inner;j++){
if(j == ){
temp[i][j] = temp[i][j] + temp[i-][j];
}else if(j == length_inner - ){
temp[i][j] = temp[i][j] + temp[i-][j-];
}else{
temp[i][j] = (temp[i][j] + temp[i-][j-] < temp[i][j] + temp[i-][j] ? temp[i][j] + temp[i-][j-]:temp[i][j] + temp[i-][j]); //求和最大的路径即'<'改成'>'
}
}
}
int min = temp[length-][];
for(i=;i<temp[length-].size();i++){
min = (min < temp[length-][i]?min:temp[length-][i]); //求和最大的仅做相应简单修改
}
return min;
}
};解法二：从下往上遍历,从倒数第二行开始计算每个元素与下一行与它相邻的两个元素的和，比较并保存最小值，最后triangle[0][0]即为结果
#include<iostream>
#include<vector>
using namespace std; int maxmumTotal(vector<vector<int>> &triangle)
{
vector<vector<int>> temp(triangle);
for(int i=temp.size()-;i>=;i--)
{
for(int j=;j<temp[i].size();j++)
{
temp[i][j]+=min(temp[i+][j],temp[i+][j+]);
}
}
return temp[][];
} int main()
{
int n = ;
while (cin >> n)
{
vector<vector<int>> tree;
for (int i = ; i < n; ++i)
{
vector<int> row;
for (int j = ; j <= i; ++j)
{
int temp = ;
cin >> temp;
row.push_back(temp);
}
tree.push_back(row);
}
cout<<maxmumTotal(tree);
}
system("pause");
}