在处理多个矩阵连续相乘（矩阵链乘法）时，不同的结合顺序会导致标量乘法次数的巨大差异。对于少量矩阵的相乘，枚举所有情况即可找到最优解；但当矩阵数量增加时，必须借助算法来寻找最优的括号化方案，以最小化计算代价。以下将分别探讨基于记忆化搜索和动态规划的两种高效求解策略。

自顶向下：记忆化搜索

记忆化搜索（Memoization）通过递归分解问题，并利用二维缓存数组记录已解决的子问题结果，从而避免重复计算。这种方法保留了递归的直观逻辑，同时将时间复杂度从指数级降低到多项式级。在实现时，我们使用一维数组存储矩阵的维度信息，其中第 i 个矩阵的维度为 dims[i-1] × dims[i]。

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// 递归函数，计算矩阵链 dims[start...end] 的最小乘法次数
int solveMemoized(const vector<int>& dims, int start, int end, vector<vector<int>>& cache) {
    // 单个矩阵无需进行乘法运算
    if (start == end) {
        return 0;
    }
    
    // 如果子问题已经计算过，直接返回缓存结果
    if (cache[start][end] != -1) {
        return cache[start][end];
    }
    
    int minCost = INT_MAX;
    
    // 尝试所有可能的分割点
    for (int split = start; split < end; ++split) {
        int cost = solveMemoized(dims, start, split, cache) 
                 + solveMemoized(dims, split + 1, end, cache) 
                 + dims[start - 1] * dims[split] * dims[end];
                 
        if (cost < minCost) {
            minCost = cost;
        }
    }
    
    // 将最优解存入缓存并返回
    cache[start][end] = minCost;
    return minCost;
}

int main() {
    int numMatrices;
    if (!(cin >> numMatrices)) return 0;
    
    // 维度数组大小为 numMatrices + 1
    vector<int> dims(numMatrices + 1);
    for (int i = 0; i <= numMatrices; ++i) {
        cin >> dims[i];
    }
    
    // 初始化缓存表，-1 表示尚未计算
    vector<vector<int>> cache(numMatrices + 1, vector<int>(numMatrices + 1, -1));
    
    int minMultiplications = solveMemoized(dims, 1, numMatrices, cache);
    cout << minMultiplications << endl;
    
    return 0;
}

自底向上：动态规划

自底向上的动态规划（Dynamic Programming）摒弃了递归调用，通过迭代的方式按矩阵链长度递增的顺序填充状态表。这种方法不仅避免了递归带来的函数调用栈开销，还在空间局部性上表现更优，是解决此类区间DP问题的标准范式。

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main() {
    int numMatrices;
    if (!(cin >> numMatrices)) return 0;
    
    vector<int> dims(numMatrices + 1);
    for (int i = 0; i <= numMatrices; ++i) {
        cin >> dims[i];
    }
    
    // dp[i][j] 表示计算矩阵链 Ai 到 Aj 所需的最小标量乘法次数
    vector<vector<int>> dp(numMatrices + 1, vector<int>(numMatrices + 1, 0));
    
    // chainLen 代表当前计算的矩阵链长度，从 2 开始递增
    for (int chainLen = 2; chainLen <= numMatrices; ++chainLen) {
        for (int start = 1; start <= numMatrices - chainLen + 1; ++start) {
            int end = start + chainLen - 1;
            dp[start][end] = INT_MAX;
            
            // 遍历分割点，寻找最小代价
            for (int split = start; split < end; ++split) {
                int cost = dp[start][split] + dp[split + 1][end] 
                         + dims[start - 1] * dims[split] * dims[end];
                         
                if (cost < dp[start][end]) {
                    dp[start][end] = cost;
                }
            }
        }
    }
    
    // 输出整个矩阵链的最小乘法次数
    cout << dp[1][numMatrices] << endl;
    
    return 0;
}