程序填空题：Ordering Matrix Multiplications Problem

In which order can we compute the product of N matrices with minimal computing time?

Let r contains number of columns for each of the N matrices,

and r[ 0 ] is the number of rows in matrix 1.

Please complete the following function OptMatrix( ) to get the minimum number of multiplications left in M[ 1 ][ N ] .

```c++
/* N1 is N+1 */
void OptMatrix( const long r[ ], int N, long M[ ][N1] )
{ int i, j, k, L;
long ThisM;
for( i = 1; i <= N; i++ ) @@[M[ i ][ i ] = 0](2);
for( k = 1; k < N; k++ ) /* k = j - i */
for( i = 1; i <= N - k; i++ ) { /* For each position */
j = i + k; M[ i ][ j ] = Infinity;
for( L = i; L < j; L++ ) {
ThisM = @@[M[ i ][ L ] + M[ L + 1 ][ j ] + r[ i - 1 ] * r[ L ] * r[ j ]](2);
if ( @@[ThisM < M[ i ][ j ]](2) ) /* Update min */
M[ i ][ j ] = ThisM;
} /* end for-L */
} /* end for-Left */
}

```






答案：
第1空：M[ i ][ i ] = 0

第2空：M[ i ][ L ] + M[ L + 1 ][ j ] + r[ i - 1 ] * r[ L ] * r[ j ]

第3空：ThisM < M[ i ][ j ]