洛谷 P1216 数字三角形 Number Triangles - Solution

1. 题目数据 (Problem Metadata)

• 题目类型：传统题
• 题目链接：P1216 [IOI 1994 / USACO1.5] 数字三角形 Number Triangles - 洛谷
• 时间限制：1.00s
• 内存限制：125.00MB

2. 题意简述 (Problem Summary)

给定一个 $r$ 行的数字三角形（$1 \le r \le 1000$），第 $i$ 行有 $i$ 个整数 $a_{i,j} \in [0, 100]$。从顶点 $a_{1,1}$ 出发，每一步只能走到正下方 $a_{i+1,j}$ 或右下方 $a_{i+1,j+1}$，求一条到达底行的路径，使经过数字之和最大。即：

$$
\max_{P \in \text{合法路径}} \sum_{(i,j) \in P} a_{i,j}
$$

3. 朴素解法 (Brute-Force)

最直接的想法是 DFS 枚举所有路径：从 $(1,1)$ 出发，每步尝试向下或向右下，到达底行后更新全局最大值。

• 每一步有 2 种选择，路径长度为 $r-1$ 步。
• 总路径数：$2^{r-1}$ 条，每条路径需要 $O®$ 求和。

时间复杂度：$O(2^r \cdot r)$，$r \ge 30$ 即超时。题目要求 $r = 1000$，$2^{1000}$ 远超宇宙原子数，完全不可行。即使加入最优化剪枝（当前和 + 剩余行最大可能和 $\le$ 当前最优），对于三角形中间数值分布均匀的情况，剪枝效果极差。总而言之，必须换思路。

4. 核心解法 (Main Solution)

特殊性质

数字三角形具有完美的 最优子结构 和 无后效性，这是 DP 可解的充要条件。

关键突破

注意到：到达 $(i,j)$ 的最大和，只与到达其两个"前驱" $(i-1,j-1)$ 和 $(i-1,j)$ 的最大和有关，与这些前驱自身的路径毫无关系。因此我们可以 自顶向下逐行递推，每行每个位置只计算一次，避免指数级重复枚举。这就是动态规划的 时间换空间：我们存储了到每个位置的最大和，从而简化了原本重复的搜索过程。

推导过程

下面推导动态规划的状态转移方程：

第 1 步：定义状态

设 $dp[i][j]$ 表示从顶点 $(1,1)$ 走到 $(i,j)$ 能获得的最大数字和。

第 2 步：初始状态

$$
dp[1][1] = a_{1,1}
$$

第 3 步：状态转移

$(i,j)$ 只能从 $(i-1,j-1)$（左上方）或 $(i-1,j)$（正上方）走来。因此：

$$
dp[i][j] = \max\big(dp[i-1][j-1],; dp[i-1][j]\big) + a_{i,j}
$$

边界处理：

• $j = 1$（每行最左）：只能从 $(i-1,1)$ 走来，$dp[i][1] = dp[i-1][1] + a_{i,1}$。
• $j = i$（每行最右）：只能从 $(i-1,i-1)$ 走来，$dp[i][i] = dp[i-1][i-1] + a_{i,i}$。

第 4 步：答案

底行每个位置都可能成为路径终点：

$$
\text{ans} = \max_{1 \le j \le r}; dp[r][j]
$$

5. 正确性证明 (Proof of Correctness)

DP 正确性需证两点：

（1）最优子结构

设 $P^$ 是以 $(i,j)$ 为终点的最优路径。若 $P^$ 经过 $(i-1,k)$（其中 $k = j-1$ 或 $k = j$），则 $P^$ 从 $(1,1)$ 到 $(i-1,k)$ 的子路径必然也是到达 $(i-1,k)$ 的最优路径。否则，将该子路径替换为更优者，$P^$ 会变得更优，矛盾。因此，此问题具有最优子结构性质。

（2）无后效性

$dp[i][j]$ 的值只由 $dp[i-1][j-1]$ 和 $dp[i-1][j]$ 决定，与这两个值从哪条路径来完全无关。因此，递推顺序（逐行、行内任意序）不会影响结果的正确性，只需要保证每次递推用到的值已经被计算，问题具有无后效性。

由（1）（2） 可知，本问题可以用动态规划解决，上述递推式正确，证毕。

6. 复杂度分析 (Complexity)

• 时间复杂度：$O(r^2)$。共 $r$ 行，第 $i$ 行 $i$ 个状态，每个状态 $O(1)$ 转移。$r \le 1000$ 时约 $5 \times 10^5$ 次运算，在 1s 时限内轻松通过。

• 空间复杂度：$O(r^2)$。二维数组 $dp[1005][1005]$ 占约 4 MB（int 型），远低于典型内存限制。

• 滚动数组优化：观察到 $dp[i][\cdot]$ 只依赖 $dp[i-1][\cdot]$，可以用两个一维数组交替滚动，将空间降至 $O®$。但对 $r=1000$ 来说，$O(r^2)$ 已经完全足够，不必为省内存引入额外编码复杂度。

7. 实现细节与避坑指南 (Implementation Details)

8. 参考代码 (Reference Code)

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

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int n;
int a[N][N], dp[N][N];

int main() {
    ios::sync_with_stdio(false);

    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++) {
            if (j == 1)
                dp[i][j] = dp[i - 1][j] + a[i][j];          // 最左列
            else if (j == i)
                dp[i][j] = dp[i - 1][j - 1] + a[i][j];      // 最右列
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j];
        }
    }

    // 取底行最大值
    int ans = 0;
    for (int j = 1; j <= n; j++)
        ans = max(ans, dp[n][j]);

    cout << ans << endl;
    return 0;
}

9. 补充说明 (Additional Notes)

• 题目渊源：本题出自 IOI 1994（国际信息学奥林匹克竞赛第 6 届），是 DP 首次作为 IOI 考点进入竞赛界的标志性题目。彼时动态规划刚被引入信息学竞赛，从这道"数字三角形"开始，DP 逐渐成为 OI/ICPC 的核心方法论之一。这也是为什么它始终是 DP 入门教学的首选例题——它足够纯粹，完美展示了 DP 的"最优子结构 + 无后效性"两个本质特征，没有任何多余技巧。

• 与 DAG 的关系：从更抽象的视角看，数字三角形可视为一种 DAG 最长路 问题。将每个格子看作节点，向下/右下走看作有向边，边权为目标格子的值，问题等价于求 DAG 上源点到任意汇点的最长路径。这类问题的统一解法即拓扑序 DP。事实上，DP 与 DAG 拓扑有密切关系。

• 反向递推（自底向上）：也可以定义 $dp[i][j]$ 为从 $(i,j)$ 走到底行的最大和，转移为 $dp[i][j] = a_{i,j} + \max(dp[i+1][j], dp[i+1][j+1])$，答案是 $dp[1][1]$。这种写法不需要最后扫描底行取 $\max$，代码更短，但本质相同。

• 变种题目：

  • 求最小路径和（将 $\max$ 改为 $\min$，注意初始化）。
  • 输出具体路径（DP 时额外记录前驱，最后从底行最优终点回溯）。
  • 三角形变为矩形网格（经典「最小路径和」/「不同路径」问题）。
  • 允许多次跳跃或带权重的走法（图论最短路模型）。