HDU 2048 數塔問題：經典動態規劃從底向上求最大路徑和

題目大意

給定高度 N (≤100) 的數塔，第 i 行有 i 個整數（0~99）。從頂點出發，每步只能走到下一行相鄰節點，求到底層的最大路徑和。多測試用例。

動態規劃狀態定義

• dp[i][j]：從頂點走到第 i 行第 j 個節點的最大路徑和（0-based 或 1-based 均可）。

狀態轉移方程

// 邊界：左邊只能從左上來，右邊只能從右上來
dp[i][0]     = dp[i-1][0]     + val[i][0];
dp[i][i]     = dp[i-1][i-1]   + val[i][i];
// 中間：取左上、右上最大值
dp[i][j]     = max(dp[i-1][j-1], dp[i-1][j]) + val[i][j];  (1 ≤ j < i)

優化：原地修改數組

無需額外 dp 數組，直接在輸入數組上累加，空間 O(1) 額外空間。

AC 代碼

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

int main() {
    int C, n, val[105][105];
    cin >> C;
    while (C--) {
        cin >> n;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j <= i; ++j)
                cin >> val[i][j];

        for (int i = 1; i < n; ++i) {
            val[i][0] += val[i-1][0];
            val[i][i] += val[i-1][i-1];
            for (int j = 1; j < i; ++j)
                val[i][j] += max(val[i-1][j-1], val[i-1][j]);
        }

        int ans = *max_element(val[n-1], val[n-1] + n);
        cout << ans << endl;
    }
    return 0;
}

關鍵點總結

結語

數塔問題是 DP 入門的經典模型，展示了「最優子結構」與「重疊子問題」特性。掌握其邊界處理與轉移邏輯，對解決更複雜的路徑類 DP（如三角形、矩陣、樹形 DP）極有幫助。