3. 设计

 1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn = 1000 + 10;
 5 const int inf = 0x3f3f3f3f;
 6 int f[maxn][maxn];    //f[i][j]表示i~j区间的最优解 
 7 int s[maxn][maxn];    //s[i][j]表示i~j区间的分割点 
 8 int n;
 9 int P[maxn];
10 int main() {
11     scanf("%d", &n);
12     for (int i = 0; i <= n; ++i)scanf("%d", &P[i]);
13     for (int i = 1; i <= n; ++i)f[i][i] = 0;
14     for (int len = 2; len <= n; ++len) {            //枚举区间长度 
15         for (int l = 1; l + len - 1 <= n; ++l) {        //枚举左边界 
16             int r = l + len - 1;
17             f[l][r] = inf;
18             s[l][r] = 0;
19             for (int i = l; i < r; ++i) {           //枚举割点 
20                 if (f[l][i] + f[i + 1][r] + P[l - 1] * P[i] * P[r] < f[l][r]) {
21                     f[l][r] = f[l][i] + f[i + 1][r] + P[l - 1] * P[i] * P[r];
22                     s[l][r] = i;
23                 }
24             }
25         }
26     }
27     printf("%d
", f[1][n]);
28 }

4. 分析

T(n)=O(n^3)

5. 源码

https://github.com/JayShao-Xie/algorithm-work/blob/master/Matrix_Chain.cpp