AcWing 898. 数字三角形

◎

本节目标

从三角形底部向上合并两个孩子，求根到叶的最大路径和。

返回网格与路径动态规划框架

查看 AcWing 原题

题意与约束

从三角形顶点走到最后一行，每一步只能走到下一行相邻两个数之一，求路径数字和最大值。

第一反应与重复子问题

从一个位置到终点有两条下一步，直接枚举有指数路径；同一位置到末行的最优后缀会被多次请求。

状态定义与转移推导

自底向上定义 dp[c] 为下一行位置 c 到底的最大和。当前位置更新为 triangle[r][c]+max(dp[c],dp[c+1])。

正确性依据

任意从当前位置开始的路径第一步只能进入两个孩子之一，最佳后缀由归纳假设给出，取更大者覆盖全部路径。

样例执行过程

从最后一行初始化后逐层合并，官方三角形顶点最终得到 30；单个 -5 必须返回 -5，不能用零代替路径。

代码实现

C++

C++17

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

int maxPathSum(const vector<vector<int>>& triangle) {
    vector<int> dp = triangle.back();
    for (int row = static_cast<int>(triangle.size()) - 2; row >= 0; row--) {
        for (int col = 0; col <= row; col++) {
            dp[col] = triangle[row][col] + max(dp[col], dp[col + 1]);
        }
    }
    return dp[0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<vector<int>> triangle(n);
    for (int row = 0; row < n; row++) {
        triangle[row].resize(row + 1);
        for (int& value : triangle[row]) {
            cin >> value;
        }
    }
    cout << maxPathSum(triangle) << '\n';
    return 0;
}

Python

Python 3

import sys


def max_path_sum(triangle: list[list[int]]) -> int:
    dp = triangle[-1].copy()
    for row in range(len(triangle) - 2, -1, -1):
        for col in range(row + 1):
            dp[col] = triangle[row][col] + max(dp[col], dp[col + 1])
    return dp[0]


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    triangle: list[list[int]] = []
    index = 1
    for row in range(n):
        triangle.append(data[index:index + row + 1])
        index += row + 1
    print(max_path_sum(triangle))


if __name__ == '__main__':
    main()

复杂度分析

时间 O(n²)，空间 O(n)。

边界与易错点

• 全负数据不能以 0 初始化。
• 必须自底向上，孩子状态才已经完整。
• 第 r 行只更新 0..r。

模式迁移

最小三角路径和只需把 max 改为 min；若要求重建路径，还要记录每步选择的孩子。