【啊哈！算法】之7、动态规划-矩阵l链乘

#include<iostream>
using namespace std;

/*
 *p[i]:矩阵Ai的列数或Ai-1的行数
 *m[i][j]:纪录Ai - Aj的矩阵连乘的最小代价
 *s[i][j]:纪录Ai - Aj之间得到最小连乘代价时的分割点
 *MAXLENGTH 矩阵链的长度
 */
#define MAXLENGTH 10

void MATRIXCHAINORDER(int p[], int m[][MAXLENGTH], int s[][MAXLENGTH])
{
	int j;
	int temp;
	for(int i = 0; i < MAXLENGTH; i++)   //i=j 的情况
	{
		m[i][i] = 0;
	}
	//i!=j的情况
	for(int len = 2; len <= MAXLENGTH; len++)
	{
		//i 从第i个矩阵开始的len个矩阵如何划分是最优
		for(int i = 0; i < MAXLENGTH - len + 1; i++)
		{
			//j是第i个数len个矩阵就是j，从i到j表示他们之间的len个矩阵如何划分
			j = i + len - 1;
			//m[i][j]是存储从i到j使用最佳划分所得的最优结果
			m[i][j] = INT_MAX; //无穷大
			//k是介于i到j-1之间的数，利用k对i到j之间的矩阵进行试探性划分，
			//从而找到最优解。
			for(int k = i; k < j; k++)
			{
				temp = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];
				if(temp < m[i][j])
				{
					m[i][j] = temp;
					s[i][j] = k;
				}
			}
		}
	}
}

void PRINTOPTIMALPARENS(int s[][MAXLENGTH], int i, int j)
{
	if(i == j)
	{
		cout << "A" << i;
	}
	else
	{
		cout << "(";
		PRINTOPTIMALPARENS(s, i, s[i][j]);
		PRINTOPTIMALPARENS(s, s[i][j]+1, j);
		cout << ")";
	}
}

//重叠子结构
int RECURSIVEMATRIXCHAIN(int p[], int m[][MAXLENGTH], int s[][MAXLENGTH], int i, int j)
{
	int temp;
	if(i == j)
		return 0;
	int u = RECURSIVEMATRIXCHAIN(p, m, s, i, i) + RECURSIVEMATRIXCHAIN(p, m, s, i + 1, j) + p[i - 1]*p[i]*p[j];
	s[i][j] = i;
	for(int k = i + 1; k < j; k++)
	{
		temp = RECURSIVEMATRIXCHAIN(p, m, s, i, k) + RECURSIVEMATRIXCHAIN(p, m, s, k + 1, j) + p[i - 1]*p[k]*p[j];
		if(temp < u)
		{
			u = temp;
			s[i - 1][j - 1] = k;
		}
	}
	return u;
}

//备忘录
int LOOKUPCHAIN(int p[], int m[][MAXLENGTH], int s[][MAXLENGTH], int i, int j)
{
	int temp;
	//检查m[i][j]
	if(m[i][j] < INT_MAX)
		return m[i][j];
	if(i == j)
	{
		m[i][j] = 0;
	}
	else
	{
		//递归寻找k，试探划分，最终找到最优解
		for(int k = i; k < j; k++)
		{
			temp = LOOKUPCHAIN(p, m, s, i, k) + LOOKUPCHAIN(p, m, s, k+1, j) + p[i-1]*p[k]*p[j];
			if(temp < m[i][j])
			{
				m[i][j] = temp;
				s[i - 1][j - 1] = k;
			}
		}
	}
	return m[i][j];
}

void MEMOIZEDMATRIXCHAIN(int p[], int m[][MAXLENGTH], int s[][MAXLENGTH], int n)
{
	for(int i = 0; i < n; i++)
	{
		for(int j = i; j < n; j++)
		{
			m[i][j] = INT_MAX;
		}
	}
	//自底向上递归
	m[0][n - 1] = LOOKUPCHAIN(p, m, s, 0, n - 1);
}

int main(void)
{
	int p[MAXLENGTH+1] = {34, 15, 35, 25, 23, 21, 67};
	int m[MAXLENGTH ][MAXLENGTH];
	int s[MAXLENGTH ][MAXLENGTH];

	MATRIXCHAINORDER(p, m, s);
	PRINTOPTIMALPARENS(s, 0, 6);
	cout << endl;

	MEMOIZEDMATRIXCHAIN(p, m, s, 7);
	PRINTOPTIMALPARENS(s, 0, 6);
	cout << endl;

	RECURSIVEMATRIXCHAIN(p, m, s, 1, 7);
	PRINTOPTIMALPARENS(s, 0, 6);
	cout << endl;

	return 0;
}

运行结果：