NYOJ 18 The Triangle：數字三角形最大路徑和動態規劃

問題描述

給定 n 行數字三角形（n ≤ 100），從頂點到底邊，每步只能向左下或右下移動，求路徑上數字和的最大值。

動態規劃狀態定義

dp[i][j] 表示從頂點走到第 i 行第 j 個位置的最大路徑和。轉移方程：

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

邊界：dp[1][1] = a[1][1]，dp[i][0] = dp[i][i+1] = -∞（或直接在循環中判斷）。

空間優化：原地修改輸入數組

因只依賴上一行，可直接在輸入數組 A[i][j] 上累加最大和：

for (i = 1; i <= n; i++)
    for (j = 1; j <= i; j++) {
        scanf("%d", &temp);
        A[i][j] = max(A[i-1][j-1], A[i-1][j]) + temp;
    }

最終答案為 max(A[n][1..n])。

完整 AC 代碼 (C)

#include 

int A[101][101];

int max(int a, int b) { return a >= b ? a : b; }

int main() {
    int n, i, j, temp;
    while (scanf("%d", &n) == 1) {
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= i; j++) {
                scanf("%d", &temp);
                A[i][j] = max(A[i-1][j-1], A[i-1][j]) + temp;
            }
        }
        int ans = 0;
        for (j = 1; j <= n; j++)
            if (A[n][j] > ans) ans = A[n][j];
        printf("%d\n", ans);
    }
    return 0;
}

複雜度分析

• 時間：O(n²)，n ≤ 100 瞬間通過。
• 空間：O(n²) 數組，約 40 KB，可接受。若需 O(n) 空間，只保留兩行滾動數組。

經典變體

• 輸出具體路徑：需記錄前驅方向。
• 最小路徑和：將 max 改為 min。
• 矩陣網格最大路徑：同理可推廣至二維網格 DP。