【题目描述】 如例所示一个数字三角形，计算从顶到底的某处的一条路径，使该路径所经过数字总和最大。 1.一步可延左斜线向下或延右斜线向下走； 2.三角形行数小于等于100； 3.三角形中数字为0，1，2，……，99； 例： 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 【输入】 第一行输入n，表示输入n行三角形，第二行到n+1行，输入三角形每行数字。 【输出】 一行，数字总和。 【分析】 吐槽信息奥赛这本教材→_→ 这道题应该怎样思考呢？ 首先想他是要选择最长路径，第一个想法是遍历每条路径然后比较，思路没毛病，就是想怎么实现。该题是运用递推的方法，从倒数第二行开始，每个元素，看下方两步哪个大，加到该行该元素上，一直到第一行，就已经计算好总和了。 即a[i][j] (i行第j个元素) = max{a[i+1][j],a[i+1][j+1]}，最后求出来a[1][1]即最大值。
【源代码】
#include <iostream>
using namespace std;
int main()
{
int n,i,j,a[101][101];
cin >> n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
cin >> a[i][j];
for(int i=n-1;i>=1;i--)
for(int j=1;j<=i;j++)
{
if(a[i+1][j]>=a[i+1][j+1])
a[i][j] += a[i+1][j];
else a[i][j] += a[i+1][j+1];
}
cout << a[1][1] <<endl;
return 0;
}
