C++实现矩阵矩Ak的行数为 rk,列数 为 rk+1,(r1,…,r6 ) =(4 6 7 2 5 10)的连乘
时间: 2024-05-16 14:15:32 浏览: 29
根据矩阵连乘的结合律,不同的加括号方式会影响到最终的计算次数。因此,我们需要采用动态规划的方法来解决这个问题。
设 $dp[i][j]$ 表示第 $i$ 到第 $j$ 个矩阵的最小计算次数。则有状态转移方程:
$$dp[i][j] = \min_{i \leq k < j}(dp[i][k] + dp[k+1][j] + r_i \times r_{k+1} \times r_{j+1})$$
其中 $r_i$ 表示第 $i$ 个矩阵的行数,$r_{i+1}$ 表示第 $i$ 个矩阵的列数。
最终的答案为 $dp[1][6]$。
以下是 C++ 代码实现:
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 7;
int r[N] = {4, 6, 7, 2, 5, 10};
int dp[N][N];
int main()
{
memset(dp, 0x3f, sizeof dp);
for (int i = 1; i <= N; i ++ ) dp[i][i] = 0;
for (int len = 2; len <= N; len ++ )
for (int i = 1; i + len - 1 <= N; i ++ )
{
int j = i + len - 1;
for (int k = i; k < j; k ++ )
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + r[i-1] * r[k] * r[j]);
}
cout << dp[1][6] << endl;
return 0;
}
```