POJ 1163 The Triangle 詳解

題目：給定 n (≤100) 行數字三角形，每行 i 有 i 個整數（0~99）。從頂點出發，每步只能向左下或右下移動，求到達底邊的最大路徑和。

核心模型：自底向上動態規劃

定義 dp[i][j]：從 (i,j) 到底邊的最大路徑和。
轉移：dp[i][j] = val[i][j] + max(dp[i+1][j], dp[i+1][j+1])。
邊界：底行 dp[n][j] = val[n][j]。
答案：dp[1][1]。

空間優化：原地修改 / 一維陣列

因只依賴下一行，可直接在輸入陣列上原地 DP（自倒數第二行向上），或用一維 dp[j] 從右向左更新。原地修改最簡潔。

參考代碼 (C++ / Python / Java)

// C++ 原地 DP
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        vector> a(n+1, vector(n+1));
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= i; ++j)
                cin >> a[i][j];
        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;
}

# Python
def solve():
    import sys
    data = sys.stdin.read().strip().split()
    if not data: return
    it = iter(data)
    out = []
    while True:
        try:
            n = int(next(it))
        except StopIteration:
            break
        a = [[0]*(n+2) for _ in range(n+2)]
        for i in range(1, n+1):
            for j in range(1, i+1):
                a[i][j] = int(next(it))
        for i in range(n-1, 0, -1):
            for j in range(1, i+1):
                a[i][j] += max(a[i+1][j], a[i+1][j+1])
        out.append(str(a[1][1]))
    sys.stdout.write('\n'.join(out))

if __name__ == '__main__':
    solve()

// Java
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int[][] a = new int[n+2][n+2];
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= i; ++j)
                    a[i][j] = sc.nextInt();
            for (int i = n-1; i >= 1; --i)
                for (int j = 1; j <= i; ++j)
                    a[i][j] += Math.max(a[i+1][j], a[i+1][j+1]);
            System.out.println(a[1][1]);
        }
    }
}

關鍵點總結

1. 自底向上：避免遞歸棧溢出，邊界自然處理。
2. 原地修改：無需額外空間，直接覆蓋輸入陣列。
3. 多測試用例：輸入以 EOF 結束，while(cin>>n) 循環讀取。
4. 數據範圍小：n≤100，O(n²) 時間空間極小。

複雜度分析

面試延伸

• 路徑輸出：維護決策表 choice[i][j] 記錄走左/右，回溯重構路徑。
• 最小路徑和：min 替換 max。
• 三維金字塔：狀態擴展為 dp[i][j][k]，轉移考慮 3 個方向。

總結

POJ 1163 是「數字三角形 DP」的入門標準題。它展示了自底向上動態規劃的經典模式：狀態定義清晰、轉移方程簡單、空間優化自然。此模式直接適用於「最小路徑和、最大子矩陣和、棋盤取數」等網格 DP 問題。