矩阵连乘 动态规划求解

#include<iostream>
using namespace std;
const int MAX = 100;
int m[MAX][MAX], s[MAX][MAX];
int n;
int opt[MAX][MAX], path[MAX][MAX];
int p[MAX];

void matrixChain() {
	for (int i = 1; i <= n; i++)
		m[i][i] = 0;

	for (int r = 2; r <= n; r++) //对角线循环
	{
		cout << r << endl;
		for (int i = 1; i <= n - r + 1; i++) { //行循环
			int j = r + i - 1; //列的控制
			//找m[i][j]的最小值，先初始化一下，令k=i
			m[i][j] = m[i][i] + m[i + 1][j] + p[i - 1] * p[i] * p[j];
			s[i][j] = i;
			//k从i+1到j-1循环找m[i][j]的最小值
			for (int k = i + 1; k < j; k++) {
				int temp = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
				if (temp < m[i][j]) {
					m[i][j] = temp;
					//s[][]用来记录在子序列i-j段中，在k位置处
					//断开能得到最优解
					s[i][j] = k;
				}
			}

		}
	}
}


void mc(){
	for(int i=1; i<=n; i++){

	}
}


//求从矩阵 start 到 矩阵 end 的最优乘法次数
int f(int start, int end) {
	if (opt[start][end] != 0)
		return opt[start][end];
	if (start == end)
		return 0;
	if (start == end - 1) {
		return opt[start][end] = p[start - 1] * p[start] * p[end];
	}
	int min = 1000000;
	for (int i = start ; i < end; i++) {
		int temp = f(start, i) + f(i+1, end) + p[start - 1] * p[i] * p[end] ;
		if (min > temp) {
			min = temp;
		}
	}
	return opt[start][end] = min;
}

int main() {
	cin >> n;
	for (int i = 0; i <= n; i++)
		cin >> p[i];
	//测试数据可以设为六个矩阵分别为
	//A1[30*35],A2[35*15],A3[15*5],A4[5*10],A5[10*20],A6[20*25]
	//则p[0-6]={30,35,15,5,10,20,25}
	//输入：6 30 35 15 5 10 20 25
	matrixChain();
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++){
			opt[i][j] = 0;
			m[i][j] = 0;
		}


	//使用递归的方法解决
	cout << f(1, n) << endl;

	//traceback(1,n);
	//最终解值为m[1][n];
	cout << m[1][n] << endl;

//	for (int i = 0; i <= n; i++) {
//		for (int j = 0; j <= n; j++) {
//			cout << opt[i][j] << " ";
//		}
//		cout << endl;
//		for (int j = 0; j <= n; j++) {
//			cout << m[i][j] << " ";
//		}
//		cout << endl << endl;
//	}

	return 0;
}