행렬 연승 동적 기획

#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;
}