【例67.3】 数字金字塔

解题思路

dp[j]表示到当前行第j个位置的最大路径和。当前格只可能从上一行j或j-1到达，取较大值加当前数；从右向左更新一维dp，避免覆盖上一行状态。

正确性说明

任意到当前格的路径最后一步只有两个父节点，最优前缀必可替换为该父节点的最优路径。对两者取最大并加本格值完整覆盖选择，逐行归纳即成立。

易错点

一行读完后再右向左更新；最后对底行全部dp取最大，不固定终点。

复杂度

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

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int R;
    cin >> R;
    vector<long long> dp(R + 2, LLONG_MIN / 4);
    dp[1] = 0;
    for (int i = 1; i <= R; i++) {
        vector<int> row(i + 1);
        for (int j = 1; j <= i; j++)
            cin >> row[j];
        for (int j = i; j >= 1; j--)
            dp[j] = max(dp[j], dp[j - 1]) + row[j];
    }
    cout << *max_element(dp.begin() + 1, dp.begin() + R + 1) << "\n";
    return 0;
}