動態規劃經典：矩陣鏈乘法 - 從遞歸到自底向上完整解析

3. 自底向上計算

按鏈長 l = 2 到 n 遞增，對每個起點 i 計算 j = i+l-1，枚舉 k 更新 m[i][j] 和 s[i][j]。時間 O(n³)，空間 O(n²)。

4. 構造最優解

利用 s[i][j] 遞歸打印括號化方案；利用分割點遞歸實際相乘矩陣 (需實現矩陣乘法類)。

完整 C++ 實現 (核心部分)

// 矩陣類：支持乘法、輸出、隨機初始化
class Matrix {
    int row, col;
    double** val;
public:
    Matrix(int r=0, int c=0) : row(r), col(c) { alloc(); }
    Matrix operator*(const Matrix& o) const { ... }
    friend ostream& operator<<(ostream&, const Matrix&);
    Matrix init(); // 隨機填充
};

// 矩陣鏈乘 DP
void matrix_chain_order(const vector& p, vector>& m, vector>& s) {
    int n = p.size() - 1; // n 個矩陣
    m.assign(n+1, vector(n+1, 0));
    s.assign(n+1, vector(n+1, 0));
    for (int l = 2; l <= n; ++l) {
        for (int i = 1; i <= n - l + 1; ++i) {
            int j = i + l - 1;
            m[i][j] = LLONG_MAX;
            for (int k = i; k < j; ++k) {
                long long q = m[i][k] + m[k+1][j] + 1LL * p[i-1] * p[k] * p[j];
                if (q < m[i][j]) {
                    m[i][j] = q;
                    s[i][j] = k;
                }
            }
        }
    }
}

// 打印括號化方案
void print_optimal_parens(const vector>& s, int i, int j) {
    if (i == j) cout << "A" << i;
    else {
        cout << "(";
        print_optimal_parens(s, i, s[i][j]);
        print_optimal_parens(s, s[i][j]+1, j);
        cout << ")";
    }
}

// 實際相乘得到結果矩陣
Matrix multiply_chain(const vector>& s, int i, int j, const vector& mats) {
    if (i == j) return mats[i-1];
    Matrix left = multiply_chain(s, i, s[i][j], mats);
    Matrix right = multiply_chain(s, s[i][j]+1, j, mats);
    return left * right;
}

複雜度與優化

• 標準 DP：O(n³) 時間，O(n²) 空間。n ≤ 500 可接受。
• Knuth 優化 / Monge 性質：若滿足四邊形不等式，可優化至 O(n²)，但矩陣鏈乘一般不滿足。
• 實際應用中 n 通常較小 (≤ 100)，標準 DP 足夠。

教學總結

矩陣鏈乘是動態規劃的教科書級範例，完美展示了「刻畫最優結構 → 遞歸定義 → 自底向上填表 → 回溯構造解」的標準流程。掌握此題有助於理解區間 DP、最優二叉搜索樹、多邊形三角剖分等同類問題。