動態規劃入門經典：數塔問題（自底向上 DP 求最大路徑和）

數塔問題是動態規劃的教科書級入門例題。給定高度 N (≤100) 的數塔，從頂層走到底層，每步只能走到相鄰節點，求經過節點數字之和的最大值。

問題示例

    7
   3 8
  8 1 0
 2 7 4 4
4 5 2 6 5

最優路徑：7→3→8→7→5 = 30

DP 狀態與轉移

• dp[i][j]：從第 i 行第 j 個節點走到底層的最大和
• 轉移：dp[i][j] = num[i][j] + max(dp[i+1][j], dp[i+1][j+1])
• 邊界：底層 dp[n][j] = num[n][j]
• 答案：dp[1][1]

自底向上迭代實現（空間優化）

#include <stdio.h>
int num[105][105];
int main() {
    int c, n, i, j;
    scanf("%d", &c);
    while (c--) {
        scanf("%d", &n);
        for (i = 1; i <= n; i++)
            for (j = 1; j <= i; j++)
                scanf("%d", &num[i][j]);
        for (i = n-1; i >= 1; i--)
            for (j = 1; j <= i; j++)
                num[i][j] += (num[i+1][j] > num[i+1][j+1] ? num[i+1][j] : num[i+1][j+1]);
        printf("%d\n", num[1][1]);
    }
    return 0;
}

關鍵點

1. 直接在輸入數組上原地修改，無需額外 dp 數組，空間 O(1) 額外
2. 自底向上遞推順序符合依賴關系，代碼簡潔高效
3. 時間複雜度 O(N^2)，N≤100 瞬間通過

掌握此題即掌握了 DP 的核心思想：狀態定義、轉移方程、邊界條件、計算順序。