POJ 3176 Cow Bowling：動態規劃自底向上求最大路徑和

問題建模

數字三角形，從頂點向下移動（只能走左下/右下），求路徑數字和最大值。經典 DP：dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + val[i][j]。

自底向上遞推（空間優化）

int dp[351][351];  // 原地修改輸入數組即可

// 讀入數據到 dp[i][j]
for (int i = n-1; i >= 1; i--)
    for (int j = 1; j <= i; j++)
        dp[i][j] += max(dp[i+1][j], dp[i+1][j+1]);

printf("%d\n", dp[1][1]);

關鍵點

• 原地修改輸入數組，無需額外空間
• 倒序遍歷保證依賴的下一行已計算完畢
• 邊界：最後一行無需處理，作為基礎情況

複雜度分析

• 時間：O(n²) — 每個節點訪問一次
• 空間：O(1) 額外 — 復用輸入數組

擴展：路徑重構

若需輸出具體路徑，需額外記錄選擇方向（左/右），或從頂點重新貪心走一遍：if (dp[i+1][j] > dp[i+1][j+1]) go_left; else go_right;。