HDU 2084 數塔：經典動態規劃入門與空間優化

HDU 2084 是數塔（三角形）最大路徑和問題：從頂點到底邊，每步只能走左下或右下，求路徑最大和。

問題建模

三角形第 i 行有 i 個數。設 dp[i][j] 為從頂點走到位置 (i,j) 的最大和。

狀態轉移方程

dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + val[i][j]

邊界條件：
j = 1:     dp[i][1] = dp[i-1][1] + val[i][1]      (只能從左上來)
j = i:     dp[i][i] = dp[i-1][i-1] + val[i][i]    (只能從右上來)
1 < j < i: dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + val[i][j]

自底向上優化（推薦）

從倒數第二行向上更新，直接在原陣列上操作，空間 O(1) 額外空間：

for (int i = n-1; i >= 1; --i) {
    for (int j = 1; j <= i; ++j) {
        a[i][j] += max(a[i+1][j], a[i+1][j+1]);
    }
}
答案在 a[1][1]

完整 AC 代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int a[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= i; ++j)
                cin >> a[i][j];
        
        // 自底向上 DP
        for (int i = n - 1; i >= 1; --i) {
            for (int j = 1; j <= i; ++j) {
                a[i][j] += max(a[i+1][j], a[i+1][j+1]);
            }
        }
        cout << a[1][1] << '\n';
    }
    return 0;
}

複雜度分析

• 時間：O(n²)，n ≤ 100 瞬間完成
• 空間：O(n²) 存儲三角形，或 O(1) 額外空間（原地修改）

變體延伸

1. 輸出具體路徑：記錄決策方向，回溯重建
2. 最小路徑和：將 max 改為 min
3. 路徑條數統計：cnt[i][j] = (左大?cnt左:0) + (右大?cnt右:0)
4. 三維數塔：擴展到立體幾何，狀態增加一維

核心技巧總結

• 自底向上避免邊界判斷，代碼更簡潔
• 原地修改輸入陣列節省空間
• 多測試用例注意重置/覆蓋數據
• 掌握「決策依賴下一層」的典型 DP 模式

數塔問題是動態規劃入門的最佳範例，理解其狀態定義、轉移邏輯與優化技巧，為解決更複雜的 DP 問題打下堅實基礎。