矩阵连乘最小计算次数 C语言

先上代码

#include 
#include 
#include 
#include 

const int N = 330;
struct pii
{
	int first, second;
};
pii matrix[N];
int f[N][N];

void init()
{
	memset(f, 0x3f, sizeof f);
	for (int i = 0; i < N; i++) f[i][i] = 0;
}

int min(int x, int y)
{
	if (x > y) return y;
	return x;
}

int main()
{
	init();
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d%d", &matrix[i].first, &matrix[i].second);
	}
	for (int j = 1; j < n; j++)
	{
		for (int i = 1; i+j <= n; i++)
		{
			for (int k = i; k <= i + j; k++)
			{
				f[i][i+j] = min(f[i][i+j], f[i][k] + f[k + 1][i+j] + matrix[i].first * matrix[k].second * matrix[i+j].second);
			}
		}
	}
	printf("%d\n", f[1][n]);
	return 0;
}

思路

给出i，j两数 f[i][j]表示区间i到j的连乘最小次数。

用m的结构体（用pair也行），两相邻矩阵相乘的计算次数是m[i].first * m[i].second * m[i+1].second 或者m[i].first * m[i+1].first * m[i+1].second 。

推广开来就可以得出我们的动态规划f的层间关系。

层间关系

f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]+m[i].first * m[k].second * m[j].second];
极限便是f[i][i] = 0(自乘次数为0)

for循环思路

因为这里增长的线性关系是i到j的搜索宽度，所以第一层for代表宽度，第二层代表起点，这两层就构造了所有的以i为起点的所有向后宽度的搜多范围，并且先看每一个起点，遍历完所有的起点后再增加宽度。