題目來(lái)源：算法競(jìng)賽 / 數(shù)據(jù)結(jié)構(gòu)與算法課程
難度：中等
核心考點(diǎn)：動(dòng)態(tài)規(guī)劃、矩陣乘法結(jié)合律優(yōu)化

?? 題目描述

給定 n 個(gè)矩陣，第 i 個(gè)矩陣 M_i 的大小為 w_i × w_{i+1}。我們不關(guān)心矩陣內(nèi)容，只關(guān)心其維度。

我們需要將這些矩陣按順序相乘（稱為“鏈乘積”）：

由于矩陣乘法滿足結(jié)合律但不滿足交換律，我們可以選擇不同的括號(hào)化方式來(lái)減少總運(yùn)算次數(shù)。

?? 定義：一個(gè) a × b 的矩陣乘以一個(gè) b × c 的矩陣，需要 a × b × c 次標(biāo)量乘法。

目標(biāo)：計(jì)算將這 n 個(gè)矩陣進(jìn)行鏈乘積所需的最少運(yùn)算次數(shù)。

?? 輸入格式

• 第一行：一個(gè)正整數(shù) n，表示矩陣數(shù)量。
• 第二行：n + 1 個(gè)正整數(shù) w_0, w_1, ..., w_n，其中第 i 個(gè)矩陣 M_i 的維度是 w_i × w_{i+1}。

?? 輸出格式

輸出一個(gè)整數(shù)，代表最小運(yùn)算次數(shù)。

?? 輸入輸出樣例

輸入 #1

3
5 3 2 6

輸出 #1

90

? 解析：

• 矩陣1：5×3，矩陣2：3×2，矩陣3：2×6
• 方案1：(M1 × M2) × M3 → (5×3×2) + (5×2×6) = 30 + 60 = 90
• 方案2：M1 × (M2 × M3) → (3×2×6) + (5×3×6) = 36 + 90 = 126
• 最小值為 90

?? 算法思路：動(dòng)態(tài)規(guī)劃（DP）

這是一個(gè)經(jīng)典的區(qū)間 DP 問(wèn)題。

?? 狀態(tài)定義

設(shè) dp[i][j] 表示將第 i 個(gè)到第 j 個(gè)矩陣連乘所需的最小運(yùn)算次數(shù)（1 ≤ i ≤ j ≤ n）。

?? 狀態(tài)轉(zhuǎn)移

考慮在區(qū)間 [i, j] 中枚舉分割點(diǎn) k（i ≤ k < j），即：

• 先計(jì)算 M_i × ... × M_k，得到一個(gè) w_i × w_{k+1} 的矩陣；
• 再計(jì)算 M_{k+1} × ... × M_j，得到一個(gè) w_{k+1} × w_{j+1} 的矩陣；
• 最后兩者相乘，代價(jià)為 w_i × w_{k+1} × w_{j+1}。

因此狀態(tài)轉(zhuǎn)移方程為：

?? 初始化

當(dāng) i == j 時(shí)，只有一個(gè)矩陣，無(wú)需乘法：

?? 最終答案

?? C++ 實(shí)現(xiàn)代碼

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

int main() {
    int n;
    cin >> n;

    vector<int> w(n + 1);
    for (int i = 0; i <= n; ++i) {
        cin >> w[i];
    }

    // dp[i][j] 表示從第 i 個(gè)矩陣到第 j 個(gè)矩陣連乘的最小代價(jià)
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

    // 區(qū)間長(zhǎng)度 len 從 2 開(kāi)始（至少兩個(gè)矩陣才能相乘）
    for (int len = 2; len <= n; ++len) {           // len 是當(dāng)前考慮的矩陣個(gè)數(shù)
        for (int i = 1; i <= n - len + 1; ++i) {   // 起始位置 i
            int j = i + len - 1;                   // 結(jié)束位置 j
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; ++k) {          // 枚舉分割點(diǎn)
                int cost = dp[i][k] + dp[k + 1][j] + w[i - 1] * w[k] * w[j];
                if (cost < dp[i][j]) {
                    dp[i][j] = cost;
                }
            }
        }
    }

    cout << dp[1][n] << endl;
    return 0;
}

? 注意：這里 w 數(shù)組下標(biāo)從 0 開(kāi)始，而矩陣編號(hào)從 1 到 n，所以：

• 第 i 個(gè)矩陣維度是 w[i-1] × w[i]
• 因此在狀態(tài)轉(zhuǎn)移中使用 w[i-1] * w[k] * w[j]

?? 時(shí)間復(fù)雜度分析

• 狀態(tài)數(shù)：O(n2)
• 每個(gè)狀態(tài)轉(zhuǎn)移需枚舉 O(n) 個(gè)分割點(diǎn)
• 總時(shí)間復(fù)雜度：O(n3)
• 空間復(fù)雜度：O(n2)

對(duì)于 n ≤ 1000 的數(shù)據(jù)規(guī)模完全可接受。

?? 手動(dòng)模擬樣例（n=3, w=[5,3,2,6]）

? 最終結(jié)果：dp[1][3] = 90

?? 總結(jié)

• 矩陣鏈乘法是動(dòng)態(tài)規(guī)劃入門必學(xué)題，掌握它有助于理解區(qū)間 DP 和最優(yōu)子結(jié)構(gòu)。
• 關(guān)鍵在于正確設(shè)置狀態(tài)和轉(zhuǎn)移方程。
• 實(shí)際應(yīng)用中可用于優(yōu)化圖形渲染、機(jī)器學(xué)習(xí)中的張量運(yùn)算等場(chǎng)景。

?? 附錄：復(fù)制代碼按鈕（用于網(wǎng)頁(yè)文章）

如果你將本文發(fā)布在支持 HTML 的平臺(tái)（如掘金、CSDN），可添加以下代碼實(shí)現(xiàn)“一鍵復(fù)制”功能：

<button onclick="navigator.clipboard.writeText(document.getElementById('code').innerText)">?? 復(fù)制代碼</button>
<pre id="code">
// 上面的 C++ 代碼粘貼在這里
</pre>

?? 歡迎收藏、點(diǎn)贊、轉(zhuǎn)發(fā)！
如果你喜歡這類算法題解析，歡迎關(guān)注我，后續(xù)會(huì)持續(xù)更新「動(dòng)態(tài)規(guī)劃系列」、「圖論系列」、「字符串處理」等專題！