洛谷 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(r)$ 求和。

时间复杂度： $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)$ 。但对 $r=1000$ 来说， $O(r^2)$ 已经完全足够，不必为省内存引入额外编码复杂度。

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

坑点	说明
边界条件	每行最左 ( $j=1$ ) 和最右 ( $j=i$ ) 只有一条入边，不能访问 $dp[i-1][0]$ 或 $dp[i-1][i]$ （越界或读到未初始化值）。代码中需显式 `if` 判断。
数组下标从 1 开始	用 $1$ -based 索引可以自然地避免 $dp[0][\cdot]$ 的边界检查，代码更简洁。
整数范围	$a_{i,j} \le 100$ ， $r \le 1000$ ，最大路径和 $\le 100 \times 1000 = 10^5$ ，`int` 完全够用，无需 `long long`。
答案初始值	求最大值时初始化为 $0$ 即可，因为所有 $a_{i,j} \ge 0$ 。若题目允许负数，则应初始化为 $-\infty$ 。

8. 参考代码 (Reference Code)

#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 时额外记录前驱，最后从底行最优终点回溯）。
- 三角形变为矩形网格（经典「最小路径和」/「不同路径」问题）。
- 允许多次跳跃或带权重的走法（图论最短路模型）。