Multiplication Puzzle

题目解析

这道题是一道非常经典的区间动态规划 (Interval DP) 题目。

和石子合并这个题目的思路是一样的,从后(时间)往前思想

1. 核心思维：逆向思考（最后一张是谁？）

如果顺着想“第一步取哪张卡片”，你会发现之后的局面变得很复杂，因为相邻关系变了。

技巧：我们要倒着想。

假设我们只关注一段区间 [i, j]（即从第 $i$ 张卡片到第 $j$ 张卡片）。

这一段区间最终只会剩下两张卡片：边界 $i$ 和边界 $j$ 。

那么，在这一段区间里，肯定有一张卡片 $k$ 是“最后”被取走的。

当我们要取走这最后一张卡片 $k$ 时，它的左边一定是 $i$ ，右边一定是 $j$ （因为 $i$ 和 $j$ 之间的其他卡片都已经被取光了）。

此时取走 $k$ 的得分是：

\text{Cost} = A[i] \times A[k] \times A[j]

2. 动态规划定义

我们定义 $dp[i][j]$ 为：

将第 $i$ 张到第 $j$ 张卡片中间的所有卡片取走（只剩下 $i$ 和 $j$ ），所需的最小得分。

目标：求 $dp[1][N]$ 。
初始条件：
- 当 $j = i + 1$ 时（例如第1张和第2张），中间没有卡片可以取，所以 $dp[i][i+1] = 0$ 。

3. 状态转移方程

对于区间 $[i, j]$ ，我们需要枚举中间的分割点 $k$ （ $k$ 代表该区间内最后一张被取走的卡片，位置在 $i+1$ 到 $j-1$ 之间）。

总代价由三部分组成：

先把 $i$ 到 $k$ 之间的取光的最小代价： $dp[i][k]$
先把 $k$ 到 $j$ 之间的取光的最小代价： $dp[k][j]$
最后取走 $k$ 的代价： $A[i] \times A[k] \times A[j]$

公式如下：

dp[i][j] = \min_{k=i+1}^{j-1} \{ dp[i][k] + dp[k][j] + A[i] \times A[k] \times A[j] \}

4. 算法流程 (区间 DP 模板)

区间 DP 的遍历顺序很讲究，通常遵循以下三层循环：

枚举区间长度 (len)：先解决小区间（长度为2, 3…），再解决大区间。
枚举起点 (i)：确定区间的左端点，算出右端点 $j$ 。
枚举分割点 (k)：尝试每一个可能的最后一张卡片。

5. 图解演示

假设输入为：10 1 50 20 ( $N=4$ )

目标是求 $dp[1][4]$ 。

第一轮：长度 len=3 (中间隔1个数)

区间 [1, 3] (即 10, 1, 50)：
- 中间只能取 $k=2$ (也就是数字1)。
- 代价 = $10 \times 1 \times 50 = 500$ 。
- $dp[1][3] = 500$ 。
区间 [2, 4] (即 1, 50, 20)：
- 中间只能取 $k=3$ (也就是数字50)。
- 代价 = $1 \times 50 \times 20 = 1000$ 。
- $dp[2][4] = 1000$ 。

第二轮：长度 len=4 (中间隔2个数)

区间 [1, 4] (即 10, 1, 50, 20)：
- 选择 A：最后取 $k=2$ (数字1)
  - 意味着先搞定右边的 [2, 4] (变成 1和20)，再取1。
  - 代价 = $dp[1][2] + dp[2][4] + (10 \times 1 \times 20)$
  - $= 0 + 1000 + 200 = 1200$ 。
- 选择 B：最后取 $k=3$ (数字50)
  - 意味着先搞定左边的 [1, 3] (变成 10和50)，再取50。
  - 代价 = $dp[1][3] + dp[3][4] + (10 \times 50 \times 20)$
  - $= 500 + 0 + 10000 = 10500$ 。
- 比较：1200 < 10500，所以最优解是 1200。

6. C++ 代码实现

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits> // for INT_MAX

using namespace std;

const int MAXN = 105;
int arr[MAXN];
int dp[MAXN][MAXN];

int main() {
    // 优化IO
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    for (int i = 1; i <= N; ++i) {
        cin >> arr[i];
    }

    // 初始化 DP 数组
    // dp[i][i+1] 默认为 0 (相邻两张卡没法取中间的)
    // 其他初始化为一个很大的数，方便求 min
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            dp[i][j] = 0; 
        }
    }

    // 核心代码：区间 DP
    // 1. 枚举区间长度 len。
    // 最小区间包含3张卡片(左、中、右)，长度定义为右下标-左下标
    // len = 2 表示 i 和 i+2 之间有一个数
    for (int len = 2; len < N; ++len) { 
        // 2. 枚举左端点 i
        for (int i = 1; i <= N - len; ++i) {
            int j = i + len; // 计算右端点 j
            
            dp[i][j] = INT_MAX; // 先设为无穷大

            // 3. 枚举中间的分隔点 k (即最后被取走的卡片)
            // k 必须在 i 和 j 之间
            for (int k = i + 1; k < j; ++k) {
                int cost = dp[i][k] + dp[k][j] + arr[i] * arr[k] * arr[j];
                if (cost < dp[i][j]) {
                    dp[i][j] = cost;
                }
            }
        }
    }

    // 输出从 1 到 N 全部取完的最小代价
    cout << dp[1][N] << endl;

    return 0;
}

总结与提示

复杂度：这实际上是一个 $O(N^3)$ 的算法。因为 $N \le 100$ ，运算次数大约是 $100^3 = 1,000,000$ ，非常安全。
易错点：
- 循环顺序：一定要先枚举长度 len，再枚举起点 i。如果直接双层循环 i 和 j，会导致计算大区间时，小区间的值还没算出来。
- 边界：注意 k 的范围是 i+1 到 j-1，不能等于 i 或 j，因为首尾卡片不能取。

目录