『原创』算法#7 矩阵连乘（递归法）

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

#define INF 0x3f3f3f3f
#define N 6

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

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

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;

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

	return 0;
}