数字三角形

一、问题描述

给定一个 $n$ 行的数字三角形，其中的数字均为正整数。从顶点出发，每次走到下一行的左下方或右下方，直到最后一行。求经过的数字之和的最大值。

数据范围：$1\le n\le500$，$1\le a[i][j]\le10^4$。

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

例如，路径 $7\to3\to8\to7\to5$ 的数字之和为 $30$，是本例的最大值。

输入格式：第一行输入 $n$，接下来 $n$ 行输入三角形中的数字，第 $i$ 行有 $i$ 个数。

输出格式：输出最大路径和。

二、为什么考虑 DP？

​ 每一步都有两个方向，直接枚举所有路径需要考虑 $2^{n-1}$ 条路径，时间复杂度过高。如果使用贪心策略的话，每次选择下方较大的数也不一定正确。本例中，贪心可能走出 $7\to8\to1\to7\to5$，总和为 $28$，小于最优答案 $30$。

​ 注意到一个性质，从顶点走到位置$(i,j)$的最大路径值，只和其左上方和右下方的点$(i-1,j-1)、(i-1,j)$的最大路径值相关，因此因此只需保留从顶点到达该位置的最大路径和。

三、状态与转移

1. 定义状态

设 $a[i][j]$ 为第 $i$ 行第 $j$ 列的数字，定义：

$$dp[i][j]=\text{从顶点走到位置 }(i,j)\text{ 的最大路径和}$$

其中 $1\le j\le i\le n$，路径和包含当前位置的数字。

2. 推导转移

位置 $(i,j)$ 可以从上一行的两个位置到达：

• 左上方 $(i-1,j-1)$。
• 右上方 $(i-1,j)$。

选择路径和较大的来源，再加上当前位置的数字：

$$dp[i][j]=\max\bigl(dp[i-1][j-1],\ dp[i-1][j]\bigr)+a[i][j]$$

两侧边界只有一个合法来源，可以利用下面的初始化方式统一处理。

3. 初始化与边界

所有 $dp$ 值初始为 $0$，包括三角形外的辅助位置。

由于三角形中的数字均为正数，合法前驱的路径和大于 $0$，所以边界处取最大值时会选中合法前驱，无须单独判断。

从第 $1$ 行开始使用同一个转移式，顶点自然得到：

$$dp[1][1]=\max(dp[0][0],dp[0][1])+a[1][1]=a[1][1]$$

4. 统计答案

路径可以在最后一行的任意位置结束，因此答案为：

$$\max_{1\le j\le n}dp[n][j]$$

四、参考代码

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

const int N = 510;
int n, a[N][N], dp[N][N];  // 全局数组默认初始化为 0

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= i; j++) 
            cin >> a[i][j];
    
    for (int i = 1; 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;
}

共 $\frac{n(n+1)}{2}$ 个有效状态，每个状态的转移只需常数次操作，时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。

五、易错点

• 初始化条件：本题数字均为正数，因此可以用 $0$ 作为不存在的前驱的辅助值，使其被自然淘汰。
• 答案位置：答案是最后一行的最大值，不一定是 $dp[n][n]$。