题解：数字三角形最大路径和

题目分析

本题是经典的数字三角形模型问题，要求从三角形顶端出发，每次向下移动到斜对角相邻的元素，求路径和的最大值。这类问题具有明显的最优子结构和重叠子问题性质，适合用动态规划（DP）解决。

方法思路

1. 动态规划定义
   设 dp[i][j] 表示从第 i 行第 j 列的元素出发，到底层的最大路径和。

   • 对于最后一行（第 n 行），路径和即为元素本身，因此 dp[n][j] = triangle[n][j]。
   • 对于上方的行，每个位置 (i, j) 可以向下移动到 (i+1, j) 或 (i+1, j+1)，因此状态转移方程为：$$dp[i][j] = \max(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j] $$

2. 遍历顺序
   从倒数第二行（第 n-1 行）开始，自底向上计算每个位置的最大路径和。这样可以确保在计算 dp[i][j] 时，其下方的状态已经被计算完成。

3. 空间优化
   由于每次计算仅依赖下一行的数据，也可以使用一维数组优化空间复杂度至 (O(N))，但本题直接使用二维数组更直观。

解决代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#define Maxn 350+5
using namespace std;

int main() {
    int n;
    int dp[Maxn][Maxn]; // 存储三角形及动态规划结果
    cin >> n;
    for (int i = 1; i <= n; i++) // 输入三角形数据
        for (int j = 1; j <= i; j++)
            cin >> dp[i][j];
    
    for (int i = n - 1; i >= 1; i--) { // 从倒数第二行向上遍历
        for (int j = 1; j <= i; j++) {
            // 选择下方两个相邻元素中的较大值，加上当前元素
            dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + dp[i][j];
        }
    }
    cout << dp[1][1] << endl; // 顶端即为最大路径和
    return 0;
}

代码解释

1. 输入处理
   读取三角形行数 n 和各层元素，存储到二维数组 dp 中。这里 dp 既用于存储原始数据，也用于动态规划过程中的状态转移。

2. 自底向上计算

   • 从倒数第二行（i = n-1）开始，逐行向上遍历。
   • 对于每个位置 (i, j)，取其下方两个相邻位置 (i+1, j) 和 (i+1, j+1) 中的较大值，加上当前元素 dp[i][j]，更新为当前位置的最大路径和。

3. 结果输出
   遍历完成后，dp[1][1] 即为从顶端出发到底层的最大路径和，直接输出即可。

复杂度分析

• 时间复杂度：(O(N^2))，其中 (N) 为三角形行数。需要遍历每个元素一次，总共有 (1 + 2 + \dots + N \approx N^2/2) 个元素。
• 空间复杂度：(O(N^2))，使用二维数组存储状态。若优化为一维数组，空间复杂度可降至 (O(N))。

该方法通过动态规划高效地解决了问题，确保在合理时间内处理最大规模输入（(N=350)）。