三角形最佳路径问题

题目描述

给定一个高度为 $h$ （ $1 \leqslant h \leqslant 100$ ）的数字三角形，第 $r$ 行有 $r$ 个正整数。从顶部出发，每一步只能走到下一层正下方或右下方的数，直到最底层，求路径上数字之和的最大值。输入第一行为 $h$ ；接下来 $h$ 行，第 $r$ 行为该行的 $r$ 个整数，用空格分隔；输出最佳路径的数字之和。例如输入 5，7，3 8，8 1 0，2 7 4 4，4 5 2 6 5 时输出 30。

思路

设 $f(r, c)$ 表示从 $(r, c)$ 出发到底部的最大路径和，则 $f(r, c) = a(r, c) + \max(f(r+1, c), f(r+1, c+1))$ ，最底层 $f(h, c) = a(h, c)$ ，答案为 $f(1, 1)$ 。递推只依赖下一行，用一维数组自底向上滚动即可，时间复杂度 $O(h^2)$ 。

参考代码

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
27#!/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 03:27
# update_at: 2026-10-04 10:27

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 三角形高度，也是最底层一行里的数字个数

    tri: list[list[int]] = []
    for i in range(1, n + 1):
        tri.append([next(data) for _ in range(i)])  # 第 i 行共 i 个数

    dp = tri[-1][:]  # 最底层 dp 初值
    for r in range(n - 2, -1, -1):
        dp = [tri[r][j] + max(dp[j], dp[j + 1]) for j in range(r + 1)]

    print(dp[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/**
 * 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 08:09
 * update_at: 2026-10-05 08:09
 */

// 数字三角形：自底向上 DP，dp[j] 表示从当前行第 j 列出发到底部的最大路径和。

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

typedef long long ll;

const int MAXH = 105; // h <= 100

int h;             // 三角形高度
ll tri[MAXH][MAXH]; // tri[r][j] 表示第 r 行第 j 列的数字（下标从 1 开始）
ll dp[MAXH];        // 滚动数组：dp[j] = 从当前行第 j 列出发到底部的最大路径和

int main() {
    scanf("%d", &h);
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= i; j++)
            scanf("%lld", &tri[i][j]);

    // 初始化为最底层一行：从底层出发的最大和就是自身
    for (int j = 1; j <= h; j++) dp[j] = tri[h][j];

    // 自底向上递推：f(r,j) = a(r,j) + max(f(r+1,j), f(r+1,j+1))
    for (int i = h - 1; i >= 1; i--)
        for (int j = 1; j <= i; j++)
            dp[j] = tri[i][j] + max(dp[j], dp[j + 1]);

    printf("%lld\n", dp[1]);
    return 0;
}

三角形最佳路径问题

目录

题目描述

思路

参考代码