【例9.2】数字金字塔

题目描述

有一个 $R$ 层的数字金字塔，第 $i$ 层有 $i$ 个非负整数。一条路径从最高点出发，每步只能走到左下方或右下方的点，最终停在第 $R$ 层任意位置，路径的值为经过的所有数字之和，求这个和的最大值。输入：第一行为 $R$ （ $1 \leqslant R \leqslant 1000$ ），随后 $R$ 行依次给出金字塔每一层的整数，所有数不超过 $100$ ；输出：单独一行，输出可能得到的最大和。样例输入（ $5$ 层，逐行给出）：5 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11。样例输出：86，对应最优路径 $13 \to 8 \to 26 \to 15 \to 24$ 。

思路

记 $f(i,j)$ 为从 $(i,j)$ 出发走到底部的最大数字和，则 $f(i,j) = a_{i,j} + \max(f(i+1,j),\, f(i+1,j+1))$ ，且 $f(R,j) = a_{R,j}$ 。自底向上逐层递推，答案即 $f(1,1)$ ；每层只依赖下一层，用一维数组滚动即可，时间 $O(R^2)$ 、空间 $O(R)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 02:15
# update_at: 2026-09-30 02:15

import sys


def solve() -> None:
    """自底向上滚动一维数组：best[c] 表示"从当前行第 c 列出发到底部"的最大路径和。"""
    data = iter(map(int, sys.stdin.buffer.read().split()))
    R = next(data)
    rows = [[next(data) for _ in range(i + 1)] for i in range(R)]  # 第 i 行有 i+1 个数

    best = rows[-1]  # 最后一行的点只能停在原地，出发和就是它自己
    for row in reversed(rows[:-1]):
        # 第 c 列只能走向正下方的 c 或右下方的 c+1，继承两支里较大的那个
        best = [v + max(best[c], best[c + 1]) for c, v in enumerate(row)]

    print(best[0])


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 07:20
 * update_at: 2026-10-05 07:20
 */

#include <cstdio>

typedef long long ll;

const int MAXR = 1005;

int r;                 // 金字塔的行数
ll a[MAXR][MAXR];      // a[i][j] 表示第 i 行第 j 列的数字
ll best[MAXR];         // best[c] 表示"从当前行第 c 列出发走到底部"的最大路径和

// 自底向上逐层递推：f(i,c) = a[i][c] + max(f(i+1,c), f(i+1,c+1))
// 用一维数组滚动，空间 O(R)
void solve() {
    // 初始时 best 就是最后一行自己：最后一行的点走到底部就是停在原地
    for (int c = 1; c <= r; ++c)
        best[c] = a[r][c];

    // 从倒数第二行往上，每层用下一层的 best 更新
    // 第 c 列的两个后继是下一层的 c 列和 c+1 列，取较大的那个转移
    for (int i = r - 1; i >= 1; --i)
        for (int c = 1; c <= i; ++c)
            best[c] = a[i][c] + (best[c] > best[c + 1] ? best[c] : best[c + 1]);

    printf("%lld\n", best[1]);
}

int main() {
    scanf("%d", &r);
    for (int i = 1; i <= r; ++i)
        for (int c = 1; c <= i; ++c)
            scanf("%lld", &a[i][c]);
    solve();
    return 0;
}