POJ 1651 Multiplication Puzzle：區間 DP 求最小乘法代價

• 邊界：dp[l][l+1] = 0（無內部元素）。
• 遞歸 + 記憶化 或 區間長度遞增迭代均可。

代碼實現（遞歸 + 記憶化）

int a[105], dp[105][105];
int n;

int dfs(int l, int r) {
    if (l + 1 >= r) return 0; // 區間長度 ≤ 2
    if (dp[l][r] != -1) return dp[l][r];
    int ans = INF;
    for (int k = l+1; k < r; ++k)
        ans = min(ans, dfs(l, k) + dfs(k, r) + a[l]*a[k]*a[r]);
    return dp[l][r] = ans;
}

int main() {
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) cin >> a[i];
        memset(dp, -1, sizeof dp);
        cout << dfs(1, n) << endl;
    }
    return 0;
}

複雜度

• 狀態數：O(n²)，n ≤ 100。
• 每狀態枚舉 O(n) 分割點，總時間 O(n³) ≈ 10⁶，極快。
• 空間 O(n²)。

核心洞察

「最後移除誰」決定了左右子區間獨立計算，這是區間 DP 的典型「最優子結構」。代價公式 a[l]*a[k]*a[r] 反映了移除 k 時其鄰居已固定為區間端點。