ZOJ 1602 乘法拼圖：矩陣鏈乘法的動態規劃解法

問題描述

給定一排卡片，每張卡片上有一個數字。每次操作可以拿走任意一張非首尾的卡片，拿走第 i 張卡片時，得分增加 card[i-1] * card[i] * card[i+1]。重複此過程直到只剩首尾兩張卡片。目標是找到最小的總得分和。

動態規劃分析

這是一個經典的區間動態規劃問題，類似於矩陣鏈乘法優化。定義 dp[i][j] 為移除區間 (i, j) 內所有卡片（即第 i+1 到 j-1 張）所需的最小乘積和。最終答案為 dp[1][N]。

狀態轉移方程

dp[i][j] = min{ dp[i][k] + dp[k][j] + C[i] * C[k] * C[j] }  (i < k < j)

其中 k 為區間 (i, j) 內最後被移除的卡片。移除 k 時，其左右鄰居必定是 i 和 j（因為區間內其他卡片已先被移除），因此產生的乘積為 C[i] * C[k] * C[j]。

基礎情況

• dp[i][i] = 0（區間無卡片）
• dp[i][i+1] = 0（區間僅有一張卡片，無法移除）

算法實現

按區間長度從小到大進行 DP 計算。時間複雜度 O(N^3)，空間複雜度 O(N^2)，滿足 N ≤ 100 的限制。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX = 105;
int dp[MAX][MAX];
int cards[MAX];

int main() {
    int N;
    while (scanf("%d", &N) == 1) {
        memset(dp, 0x3f, sizeof(dp)); // 初始化為極大值
        for (int i = 1; i <= N; ++i) {
            scanf("%d", &cards[i]);
            dp[i][i] = dp[i][i + 1] = 0;
        }
        for (int len = 2; len < N; ++len) { // 區間長度（卡片數+1）
            for (int i = 1; i + len <= N; ++i) {
                int j = i + len;
                for (int k = i + 1; k < j; ++k) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cards[i] * cards[k] * cards[j]);
                }
            }
        }
        printf("%d\n", dp[1][N]);
    }
    return 0;
}

關鍵點總結

• 區間 DP 的核心在於「最後一步」的逆向思考：確定最後移除的卡片 k，將問題分解為左右兩個獨立子問題。
• 初始化 dp 陣列時需使用足夠大的值（如 0x3f3f3f3f），避免干擾 min 運算。
• 題目允許多組測試數據，需在循環中重置陣列。