设$n$个矩阵序列，其中第i个矩阵是$p[i-1]*p[i]$阶矩阵，给定矩阵链的向量$P$，求一种乘法次序，使得基本运算的总次数最小。
设$A[i][j]$为$\prod_{k=i}^{j}{a[k]}$
设$F[i][j]$为$A[i][j]$的最少运算次数。
$F[i][j]=min(f[i][k]+f[i+1][j]+p[i-1]*p[k]*p[j])$
1 for (int len = 2; len <= n; ++len) { 2 for (int i = 1; i + len - 1 <= n; ++i) { 3 int j = i + len - 1; 4 f[i][j] = inf; 5 s[i][j] = 0; 6 for (int k = i; k < j; ++k) { 7 int res = f[i][k] + f[k + 1][j] + p[i - 1] * p[k] * p[j]; 8 if (res < f[i][j]) { 9 f[i][j] = res; 10 s[i][j] = k; 11 } 12 } 13 } 14 }
复杂度：$O(n^3)$
https://github.com/Big-Kelly/Algorithm
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 const int inf = 2e9 + 7; 5 const ll Inf = 1e18 + 7; 6 const int maxn = 3e3 + 5; 7 const int mod = 1e9 + 7; 8 9 int f[maxn][maxn], s[maxn][maxn]; 10 int p[maxn]; 11 int n; 12 13 int main() { 14 scanf("%d", &n); 15 for (i = 0; i <= n; ++i) scanf("%d", &p[i]), f[i][i] = 0; 16 for (int len = 2; len <= n; ++len) { 17 for (int i = 1; i + len - 1 <= n; ++i) { 18 int j = i + len - 1; 19 f[i][j] = inf; 20 s[i][j] = 0; 21 for (int k = i; k < j; ++k) { 22 int res = f[i][k] + f[k + 1][j] + p[i - 1] * p[k] * p[j]; 23 if (res < f[i][j]) { 24 f[i][j] = res; 25 s[i][j] = k; 26 } 27 } 28 } 29 } 30 printf("%d\n", f[1][n]); 31 }
原文：https://www.cnblogs.com/zhang-Kelly/p/12744963.html
