Dynamic programming-matrix multiplied least times

#include<iostream>
using namespace std;
#define matrixes_number (4)
int matrixes_rows_number_array[matrixes_number + 1] = {2,3,10,4,5};
int matrixes_multiply_times[matrixes_number][matrixes_number];
int s[matrixes_number][matrixes_number];
int matrixs_multiply_least_times(){
   
    /*1 maxtrixes_multiply_times[i][i]*/
    for (int i = 0; i < matrixes_number; i++){
     matrixes_multiply_times[i][i]=0;
    }
    /*2 maxtrixes_multiply_times[i][i+1]*/
    for (int i = 0; i < matrixes_number - 1; i++){
     matrixes_multiply_times[i][i+1] = matrixes_rows_number_array[i]
     * matrixes_rows_number_array[i+1] * matrixes_rows_number_array[i+2];
        s[i][i+1] = i;  
    }
 /*3 maxtrixes_multiply_times[i][i+2], maxtrixes_multiply_times[i][i+3],*/
    for (int linked_matrix_number = 2; linked_matrix_number <= matrixes_number; linked_matrix_number++){
  for (int i = 0; i < matrixes_number - linked_matrix_number; i++){
   
    int k = i + 1;
    int j = linked_matrix_number + i;
    int curMin = matrixes_multiply_times[i][k]
                 + matrixes_multiply_times[k+1][j]
                 + matrixes_rows_number_array[i]
                  *matrixes_rows_number_array[j+1]
                  *matrixes_rows_number_array[k+1];
 

    int curVal = curMin;
              s[i][j] = k;

          for (k = i + 2; k < i + linked_matrix_number; k++){
           curVal = matrixes_multiply_times[i][k]
                    + matrixes_multiply_times[k+1][j]
                    + matrixes_rows_number_array[i]
                         *matrixes_rows_number_array[j+1]
                         *matrixes_rows_number_array[k+1];
           if (curVal < curMin) {curMin = curVal;s[i][j] = k;}
           
          }

          matrixes_multiply_times[i][j] = curMin;

  }
    }
}

void print_step(int s[matrixes_number][matrixes_number], int i, int j)
{
 if (i==j){return;}
 int step = s[i][j];
 cout<<step<<endl;
 print_step(s, i, step);
 print_step(s, step+1,j);
 return;
}

int main(){
 matrixs_multiply_least_times();
    print_step(s,0,3);

 cout << matrixes_multiply_times[0][3] <<endl;
}

Dynamic programming-matrix multiplied least times

原文：http://www.cnblogs.com/zhaodonglin/p/5277969.html