c++使用动态规划实现矩阵乘法运算，要求时间复杂度低

使用动态规划实现矩阵乘法可以将时间复杂度优化至 O(n^3)，以下是实现过程：

假设有 n 个矩阵需要相乘，第 i 个矩阵的维度为 d[i-1] * d[i]，其中 d[0] ~ d[n-1] 分别表示 n 个矩阵的维度。

定义 dp[i][j] 表示从第 i 个矩阵到第 j 个矩阵相乘的最小代价（即最少需要的标量乘法次数）。则有：

dp[i][j] = 0 (i == j)
dp[i][j] = min{dp[i][k]+dp[k+1][j]+d[i-1]*d[k]*d[j]} (i <= k < j)

其中，dp[i][k] 表示从第 i 个矩阵到第 k 个矩阵相乘的最小代价，dp[k+1][j] 表示从第 k+1 个矩阵到第 j 个矩阵相乘的最小代价，d[i-1]*d[k]*d[j] 表示从第 i 个矩阵到第 k 个矩阵再到第 j 个矩阵相乘的标量乘法次数。

使用上述递推公式，可以利用动态规划求解出 dp[1][n]，即从第 1 个矩阵到第 n 个矩阵相乘的最小代价。时间复杂度为 O(n^3)。

以下是 C++ 代码实现：

const int MAXN = 1005;
int d[MAXN];
int dp[MAXN][MAXN];

int matrixMultiply(int n) {
    for(int len = 2; len <= n; len++) {
        for(int i = 1; i <= n-len+1; i++) {
            int j = i + len - 1;
            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] + d[i-1]*d[k]*d[j]);
            }
        }
    }
    return dp[1][n];
}