『原创』算法#5 矩阵链乘法（备忘录法）

/*
 * @file					MemoMatrixchain.cpp
 * @brief					memorized way
 * @author/Univ.			taoxiaoxiao
 * @version					v1.0
 * @date					11-3-2013
*/
//实例 A1-A6：30X35 35X15 15X5 5X10 10X20 20X25
#include <iostream>
#include <vector>
using namespace std;

#define N 6
#define INF 0x3f3f3f3f

int m[N + 1][N + 1];

int LookupChain(vector<int>p, int i, int j)
{
	if (m[i][j] < INF)
		return m[i][j];
	if (i == j)
		m[i][j] = 0;
	else
	{
		for (int k = i; k <= j - 1; ++k)
		{
			int q = LookupChain(p, i, k) + LookupChain(p, k + 1, j)
				+ p[i - 1] * p[k] * p[j];
			if (q < m[i][j])
				m[i][j] = q;
		}
	}
	return m[i][j];
}

void MemorizedMatrixChain(vector<int>p)
{
	int n = p.size() - 1;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = i; j <= n; ++j)
			m[i][j] = INF;
	}
	LookupChain(p, 1, n);
}

int main()
{
	vector<int> p{ 30, 35, 15, 5, 10, 20, 25 };

	cout << "矩阵维度为: ";
	for (auto i = p.begin(); i < p.end(); ++i)
		cout << *i << " ";
	cout << endl;

	MemorizedMatrixChain(p);
	cout << "最小乘法次数: " << m[1][6] << endl;

	return 0;
}