我的算法书 - 数字三角形

一句话算法

数字三角形从底往上推：每个点的最优值等于自己加上下面两个点中更大的那个。

问题模型

给定一个 $n$ 层数字三角形：

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

从顶部出发，每一步只能走到下一层的左下方或右下方。要求从顶部走到最底层，使路径经过的数字和最大。

形式化地说，站在第 $i$ 层第 $j$ 个数时，下一步只能走到：

$(i+1,j)$ ；
$(i+1,j+1)$ 。

核心直觉

如果已经知道某个点下面两个点“从那里走到底最多能拿多少”，那么当前点的答案就很简单：

当前点 + max(左下答案, 右下答案)

所以不要从顶部暴力枚举所有路径。路径数量是指数级的。

反过来，从底层开始：

最底层的答案就是它自己；
倒数第二层可以直接由最底层推出；
再上一层继续推出；
最后推出顶点答案。

状态设计

定义：

dp[i][j]

表示从位置 $(i,j)$ 出发，走到最底层能得到的最大路径和。

最底层边界：

dp[n][j]=a[n][j]

状态转移

从 $(i,j)$ 出发，下一步只有两个选择：

(i+1,j),\quad (i+1,j+1)

所以：

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

最终答案是：

dp[1][1]

算法步骤

读入数字三角形。
把最后一层复制到 dp 中。
从第 n-1 层倒着枚举到第 1 层。
对每个位置 (i,j)，用下面两个状态更新：
- dp[j] 表示左下方；
- dp[j+1] 表示右下方。
最后 dp[1] 就是答案。

算法证明

核心不变量：处理完第 $i$ 层后，dp[j] 表示从位置 $(i,j)$ 出发走到底的最大路径和。

边界正确

最底层不能继续往下走，所以从 $(n,j)$ 出发的最大路径和就是：

$a[n][j]$
转移完整

从 $(i,j)$ 只能走到 $(i+1,j)$ 或 $(i+1,j+1)$ ，没有第三种选择。
最优子结构

如果下一步走左下方，后续最优值是 dp[i+1][j]；如果走右下方，后续最优值是 dp[i+1][j+1]。
取最大值

当前点必须被经过，所以加上 a[i][j]，再选择两个后继中的最大值。

因此转移正确。按层自底向上处理，所有依赖都已经提前算好，所以算法正确。

复杂度分析

三角形共有：

1+2+\cdots+n=\frac{n(n+1)}{2}

个数。

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

如果保留完整二维 dp 表，空间复杂度是 $O(n^2)$ ；竞赛中通常用一维数组。

代码实现

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

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

int main() {
    int n;
    cin >> n;

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

    vector<int> dp(n + 2, 0);
    for (int j = 1; j <= n; j++) {
        dp[j] = a[n][j];
    }

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

    cout << dp[1] << "\n";
    return 0;
}

测试用例

输入：

输出：

解释：最大路径为 7 -> 3 -> 8 -> 7 -> 5，路径和为 30。

应用分类详解

数字三角形的本质是：在一个分层 DAG 上，从后往前求每个状态的最优后缀。只要题目有“从一个起点出发，每一步走到下一层少数几个位置，求最大/最小路径代价”，就可以尝试这个模型。

一、分层路径最值

典型模式： 状态天然分层，每一步只能从第 $i$ 层走到第 $i+1$ 层。

识别信号： 出现“只能向下走”“只能向右/向下走”“每一步进入下一行或下一阶段”。

核心建模： dp[state] 表示从当前状态走到终点的最大或最小代价。

应用场景	经典题目	核心思路
数字三角形	luogu-P1216	自底向上求最大路径和
摘花生	noiopenjudge-ch0206/2728	网格中只能向右或向下

二、网格 DP 入门

典型模式： 在二维网格上移动，每个格子的值来自少数相邻格子。

识别信号： 出现“从左上到右下”“只能向右/下”“路径最大和/最小和”。

核心建模： 把行列位置作为状态，转移来自前一个可到达位置。

应用场景	经典题目	核心思路
最小路径和	LeetCode 64	从上方和左方取最小值
不同路径	LeetCode 62	方案数 DP

三、DAG 上的动态规划

典型模式： 状态之间没有环，可以按拓扑顺序计算。

识别信号： 出现“只能向后转移”“阶段单调增加”“有向无环图上的最长路”。

核心建模： 数字三角形是最简单的 DAG 最长路，边只从上一层指向下一层。

应用场景	经典题目	核心思路
挖地雷	roj-1262	DAG 最长路径
DAG 最长路	本书拓扑排序章节	按拓扑序转移

经典例题

1. luogu-P1216

数字三角形模板题。重点是明确 dp[i][j] 表示从当前位置到底的最大路径和。

2. noiopenjudge-ch0206/2728

摘花生。把三角形换成网格，转移方向变成来自上方或左方。

3. LeetCode 64

最小路径和。目标从最大值改成最小值，状态设计完全类似。

参考

旧版文章：Rbook_ejs_old/book/dynamic_programming/number_pyramid/index.md