题目描述

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

    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

二维优化到一维

C++ 代码

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

const int N = 510;
int n;
int a[N], f[N];

int main() {
    cin >> n;
    // 初始化f[N]
    // 这里 -1e9 会在计算f[i][1] 和 f[i][i] 时用到
    // 第 i 层的f[i][i] 会用到 f[i - 1][i]
    for (int i = 0; i < N; i ++ )
        f[i] = -1e9;

    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= i; j ++ ) 
        {
            cin >> a[j];
            // f[1] 的初始化
            if (i == 1 && j == 1)
                f[1] = a[j];
        }
        // 第一层状态不变，故从第二层开始计算状态
        if (i >= 2)
            for (int j = i; j >= 1; j -- ) 
                f[j] = max(f[j], f[j - 1]) + a[j];
    }
    // 在最后一层找最大值
    int res = -1e9;
    for (int i = 1; i <= n; i ++ )
        res = max(res, f[i]);

    cout << res << endl;

    return 0;
}