[IOI 1994 / USACO1.5] 数字三角形 Number Triangles

题意

给出一个数字三角形。

从顶部出发，每次只能走到下一行相邻的两个位置之一。

要求求出从顶到底的最大路径和。

思路

最直接的教学版做法是搜索所有路径：

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// brute.cpp：搜索所有从顶部到底部的路径，作为教学版和对拍基准程序。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 30;

int n;
int a[MAXN][MAXN];
int ans;

void dfs(int x, int y, int sum) {
    sum += a[x][y];
    if (x == n) {
        ans = max(ans, sum);
        return;
    }

    dfs(x + 1, y, sum);
    dfs(x + 1, y + 1, sum);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> a[i][j];
        }
    }

    dfs(1, 1, 0);
    cout << ans << '\n';
    return 0;
}

但正式解法用标准 DP 更直接。

设 dp[i][j] 表示走到第 i 行第 j 个位置时的最大路径和。

由于当前位置只可能从上一行相邻两个位置走来，所以：

dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j]

初始 dp[1][1] = a[1][1]，最后答案是最后一行中的最大值。

DP 公式

设 $dp_{i,j}$ 表示走到第 $i$ 行第 $j$ 个位置时的最大路径和。初始化：

dp_{1,1}=a_{1,1}

转移为：

dp_{i,j}=\max(dp_{i-1,j-1},\ dp_{i-1,j})+a_{i,j}

不存在的位置按 $-\infty$ 处理。最终答案为：

\max_{1\leqslant j\leqslant n} dp_{n,j}

公式解释：三角形中第 i 行第 j 个位置只能从上一行相邻的两个位置走来。选择其中路径和较大的一个，再加上当前格子的值，就是到达该位置的最优值。

样例 DP 表格

以样例为例，数字三角形为：

text

1
2
3
4
5      7
    3   8
  8   1   0
2   7   4   4
4   5   2   6   5

逐行计算 $dp_{i,j}$ ：

行 $i$	$j=1$	$j=2$	$j=3$	$j=4$	$j=5$
1	7
2	$7+3=$ 10	$7+8=$ 15
3	$10+8=$ 18	$\max(10,15)+1=$ 16	$15+0=$ 15
4	$18+2=$ 20	$\max(18,16)+7=$ 25	$\max(16,15)+4=$ 20	$15+4=$ 19
5	$20+4=$ 24	$\max(20,25)+5=$ 30	$\max(25,20)+2=$ 27	$\max(20,19)+6=$ 26	$19+5=$ 24

答案 $\max(24, 30, 27, 26, 24) = 30$ ，对应路径 $7 \to 3 \to 8 \to 7 \to 5$ 。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n;
int a[MAXN][MAXN];
int dp[MAXN][MAXN]; // dp[i][j]：走到第 i 行第 j 个数时的最大和

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> a[i][j];
        }
    }

    dp[1][1] = a[1][1];
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + a[i][j];
        }
    }

    int ans = 0;
    for (int j = 1; j <= n; j++) {
        ans = max(ans, dp[n][j]);
    }

    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n^2)$
空间复杂度： $O(n^2)$

总结

这题是数字三角形 DP 的最经典模型。

看清“一个位置只依赖上一层相邻两个位置”，就可以直接写出转移。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。