矩阵连乘问题 c++语言

矩阵连乘问题，也称为矩阵乘法链优化问题，是一个经典的计算机科学问题，通常涉及计算一系列矩阵相乘的最有效顺序，以最小化所需的总运算次数。在C++中解决这个问题可以采用动态规划的方法，比如使用二维数组或递归策略。

**动态规划解法步骤：**
1. 定义一个函数，如`dp[i][j]`表示将第i个到第j个矩阵按最优顺序连接所需要的最小乘法次数。
2. 当i == j时，直接返回0，因为单个矩阵不需要乘法。
3. 对于其他情况，遍历所有可能的中间节点k (i <= k < j)，比较当前通过k和不通过k的成本，选择最小的那个作为结果。
- 成本通常是 `dp[i][k] + dp[k+1][j] + matrix_size[i-1]*matrix_size[k]*matrix_size[j]`，其中`matrix_size` 是矩阵的尺寸。
4. 返回`min(dp[i][j])`作为整个序列的最优解。

int matrixMultiplicationChain(int A[], int N) {
    // 初始化一个二维数组
    vector<vector<int>> dp(N, vector<int>(N));

    for (int l = 1; l < N; ++l) {
        for (int i = 0; i < N - l; ++i) {
            int j = i + l;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; ++k)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] +
                                 pow(A[i], 2) * pow(A[k + 1], 2) * pow(A[j], 2));
        }
    }

    return dp[0][N - 1];
}