CodeChef Sums in a Triangle：三角形最大路徑和（自底向上 DP）

數字三角形，從頂點走到底邊，每步只能走左下或右下，求最大路徑和。行數 <100，測試用例 ~1000。

自底向上 DP

• 從倒數第二行開始向上：dp[j] = max(dp[j], dp[j+1]) + tri[i][j]
• 最終 dp[0] 即答案
• 空間優化：一維數組覆蓋

完整代碼

#include <vector>
#include <cstdio>
#include <iostream>
using namespace std;

int triPath(vector>& tri) {
    if (tri.empty()) return 0;
    vector path = tri.back();
    for (int i=tri.size()-2; i>=0; i--)
        for (int j=0; j> tri;
        for (int i=1;i<=n;i++) {
            vector tmp(i);
            for (int j=0;j

複雜度

時間 O(n^2) 每用例，總計 ~5e6 操作
空間 O(n)

經典三角形 DP，自底向上避免邊界判斷，代碼最簡潔。