基于自底向上的动态规划  1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 8 #define MAX 1000 9 using namespace std;10 11 12 int a[MAX] = { 0}, dp[MAX][MAX] = { 0},path[MAX][MAX] = { 0}, n;13 14 void matrix_chain_order(){15 for(int r = 2; r <= n; r ++ ){16 for(int i = 1; i <= n-r; i ++){17 int j = i+r-1;18 dp[i][j] =dp[i][i]+dp[i+1][j]+a[i]*a[i+1]*a[j+1];19 path[i][j] = i;20 for(int k=i+1; k < j; k ++){21 if( dp[i][j] > dp[i][k] + dp[k+1][j] + a[i]*a[k+1]*a[j+1] ){22 dp[i][j] = dp[i][k] + dp[k+1][j] + a[i]*a[k+1]*a[j+1];23 path[i][j] = k;24 }25 }26 }27 }28 }29 30 void print_optimal_parens(int i, int j){31 if( i == j ) {cout<<'A'<
           
            > T;44 while(T--){45 cin >> n ;46 memset(a,0,sizeof(a));47 for(int i = 1; i <= n; i ++ ) cin >>a[i];48 memset(dp,0,sizeof(dp));49 memset(path,0,sizeof(path));50 matrix_chain_order();51 52 cout<<"(";53 print_optimal_parens(1,n-1);54 cout<<")"<
           
          
         
        
       
      
     

 

基于备忘录的自顶向下的动态规划  1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 8 #define MAX 1000 9 #define INF 100000010 using namespace std;11 12 13 int a[MAX] = { 0}, dp[MAX][MAX] = { 0},path[MAX][MAX] = { 0}, n;14 15 int lookup_chain(int i,int j){16 if(dp[i][j] < INF) return dp[i][j];17 if(i == j ) return 0;18 int u = lookup_chain(i,i)+lookup_chain(i+1,j) + a[i]*a[i+1]*a[j+1];19 path[i][j] = i;20 for(int k = i+1; k < j; k ++ ){21 int t = lookup_chain(i,k)+lookup_chain(k+1,j)+a[i]*a[k+1]*a[j+1];22 if(t < u){23 u = t;24 path[i][j] = k;25 }26 }27 dp[i][j] = u;28 return u;29 }30 31 void print_optimal_parens(int i, int j){32 if( i == j ) {cout<<'A'<
           
            > T;45 while(T--){46 cin >> n ;47 memset(a,0,sizeof(a));48 for(int i = 1; i <= n; i ++ ) cin >>a[i];49 memset(dp,INF,sizeof(dp));50 memset(path,0,sizeof(path));51 lookup_chain(1,n);52 53 cout<<"(";54 print_optimal_parens(1,n-1);55 cout<<")"<