#include"MultiPlay.h"int storePath[20][20]={0};int main(){int multiDem[7]={30,35,15,5,10,20,25};std::cout<<multiplay_iterator(multiDem,2,5)<<std::endl;printMultiPath(3,5);}
#ifndef MULTIPLAY_H_#define MULTIPLAY_H_#include<iostream>#include<string>unsigned int multiplay_iterator(int *multiDem,int start,int end);void printMultiPath(int start,int end);#endif
#include"MultiPlay.h"int valueStore[20][20]={0};extern int storePath[20][20];unsigned int multiplay_iterator(int *multiDem,int start,int end){if(start==end)return 0;if(valueStore[start][end]!=0)return valueStore[start][end];int multiCount=655360;for(int i=start;i<end; i++){if(multiCount>(multiplay_iterator(multiDem,start,i)+multiplay_iterator(multiDem,i+1,end)+multiDem[start-1]*multiDem[i]*multiDem[end])){storePath[start][end]=i;multiCount=multiplay_iterator(multiDem,start,i)+multiplay_iterator(multiDem,i+1,end)+multiDem[start-1]*multiDem[i]*multiDem[end];}}valueStore[start][end]=multiCount;return multiCount;}void printMultiPath(int start,int end){if(start==end)return ;if(storePath[start][end]==start||storePath[start][end]==end)return;std::cout<<"A"<<start<<" * "<<"A"<<storePath[start][end]<<std::endl;std::cout<<"A"<<storePath[start][end]+1<<" * "<<"A"<<end<<std::endl;printMultiPath(start,storePath[start][end]);printMultiPath(storePath[start][end]+1,end);}
原文：http://www.cnblogs.com/yml435/p/4655536.html