假设有如下所示的一个数字金字塔，现在，要求写一个程序来查找从顶点到底部任意处结束的路径，使路径经过的数字的和最大，并输出该路径的最大和。比如以下金字塔的和最大路径的和为7+3+8+7+5=30。 7 3 2 8 1 0 2 7 4 4 4 5 2 6 5
#include
#include
#include
using namespace std;
/************************************************************************/
/*vec存储数值
maxSum当前的最大值
sum走到当前路径的之和
i, j当前处于的位置
size数字的宽度与高度*/
/************************************************************************/
/************************************************************************/
/* 查找路径之和的最大值 */
/************************************************************************/
void getMaxSum(vector
{
if (0 > i || i >= size || 0 > j || j > i)
return;
sum += vec[i][j];
(*maxSum) = max(*maxSum, sum);
getMaxSum(vec, maxSum, sum, i + 1, j, size);
getMaxSum(vec, maxSum, sum, i + 1, j + 1, size);
}
int main()
{
int size;
int maxSum;
vector
cin >> size;
for (int i = 1; i <= size; ++i)
{
vector
for (int j = 0; j < i; ++j)
cin >> v[j];
vec.push_back(v);
}
getMaxSum(vec, &maxSum, 0, 0, 0, size);
cout << maxSum << endl;
return 0;
}
