【输入形式】 第1行为一个正整数n,表示n个矩阵相乘,n≤100。 第2行为n+1个整数p0p1……pn,其中pi-1pi为矩阵Ai的行数和列数。 【输出形式】 一个整数,为最小乘法次数。使用c语言
时间: 2024-02-17 16:02:25 浏览: 86
以下是动态规划的解法,时间复杂度为O(n^3):
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int min(int a, int b) {
return a < b ? a : b;
}
int main() {
int n;
scanf("%d", &n);
int *p = (int *)malloc(sizeof(int) * (n + 1));
for (int i = 0; i < n + 1; i++) {
scanf("%d", &p[i]);
}
int **dp = (int **)malloc(sizeof(int *) * n);
for (int i = 0; i < n; i++) {
dp[i] = (int *)malloc(sizeof(int) * n);
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; 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] + p[i] * p[k + 1] * p[j + 1]);
}
}
}
printf("%d\n", dp[0][n - 1]);
for (int i = 0; i < n; i++) {
free(dp[i]);
}
free(dp);
free(p);
return 0;
}
```
输入示例:
```
3
10 100 5 50
```
输出示例:
```
7500
```
阅读全文