题目描述

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5
**输入格式**
第一行包含整数n，表示数字三角形的层数。

接下来n行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。

**输出格式**
输出一个整数，表示最大的路径数字和。

**数据范围**
1≤n≤500,
−10000≤三角形中的整数≤10000

样例

**输入样例**：
5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5
**输出样例：**
30

(从下往上加) $O(n^2)$

f[i][j]每次选取相邻的两个元素中的最大值相加
最终结果为f[1][1]

时间复杂度 O(n^2)

C++ 代码

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

const int N = 510;
int n;
int f[N][N];   //存放输入的三角形

int main()
{
    cin >> n;
    for (int i=1; i<=n; i++)
        for(int j=1; j<=i; j++)
            cin>>f[i][j];   //输入三角形


    for(int i=n-1; i; i--)   //从倒数第二行开始
        for(int j=1; j <= i; j++)
            f[i][j] += max(f[i+1][j],f[i+1][j+1]);     //每次与下一行的两个元素中最大值相加，最后加到f[1][1]为最大值

    cout<< f[1][1] <<endl;  //输出结果

    return 0;


}