动态规划：矩阵连乘问题

以下只是对此问题的一个代码实现，具体理论部分请参见王晓东《算法设计与分析》第2版3.1节 矩阵连乘问题。

#include <iostream>
#include <iomanip>


using namespace std;

#define MAX_COUNT     20

//矩阵属性
struct tagMatrixAttribute
{
  int row;
  int col;
};

//矩阵连乘加括号求解
void MatrixChain( tagMatrixAttribute mMatrix[], int nCount,
         int m[][MAX_COUNT], int s[][MAX_COUNT] )
{
  for ( int i = 0; i < nCount; ++i ) m[i][i] = 0;

  for ( int r = 1; r < nCount; ++r )
  {
    for ( int i = 0; i < nCount - r; ++i )
    {
      int j = i + r;
      //从k处断开，i <= k < j
      int k = i;
      m[i][j] = m[i][k] + m[k+1][j] 
      + mMatrix[i].row * mMatrix[k].col * mMatrix[j].col;
      s[i][j] = k;
      int nTemp = 0;
      for( k = i + 1; k < j; ++k )
      {
        nTemp = m[i][k] + m[k+1][j] 
        + mMatrix[i].row * mMatrix[k].col * mMatrix[j].col;
        if ( nTemp < m[i][j] )
        {
          m[i][j] = nTemp;
          s[i][j] = k;
        }
      }
    }
  }
}

//构造结果 
void TraceBack( int s[][MAX_COUNT], int i, int j )
{
  if ( i == j ) 
  {
    cout << "A" << i+1;
    return;
  }

  cout << "(";
  TraceBack( s, i, s[i][j] );
  TraceBack( s, s[i][j]+1, j );
  cout << ")";
}


void PrintArray( int nArray[][MAX_COUNT], int nCount )
{
  cout << left;
  for( int i = 0; i < nCount; ++i )
  {
    for ( int j = 0; j < nCount; ++j )
    {
      cout << setw(7) << nArray[i][j] << " ";
    }
    cout << endl;
  }
  cout << right;
}


int main()
{
  tagMatrixAttribute mMatrixAttrArray[] = {
    30, 35,
    35, 15,
    15, 5,
    5, 10,
    10, 20,
    20, 25
  };
//  tagMatrixAttribute mMatrixAttrArray[] = {
//    10, 100,
//    100, 5,
//    5, 50
//  };
  int nCount = _countof( mMatrixAttrArray );

  int m[MAX_COUNT][MAX_COUNT];
  int s[MAX_COUNT][MAX_COUNT];
  memset( m, 0, sizeof(m) );
  memset( s, 0, sizeof(s) );

  MatrixChain( mMatrixAttrArray, nCount, m, s );

  PrintArray( m, nCount );
  cout << endl;

  PrintArray( s, nCount );
  cout << endl;

  //构造结果
  TraceBack( s, 0, nCount-1 );
  cout << endl;

  return 0;
}

作者：山丘儿