【ADS】Dynamic Programming

发表于 | 分类于 ， | | 阅读次数:

Ordering matrix multiplication

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* r contains number of columns for each of the N matrices */ 
/* r[ 0 ] is the number of rows in matrix 1 */ 
/* Minimum number of multiplications is left in M[ 1 ][ N ] */ 
void OptMatrix( const long r[ ], int N, TwoDimArray M ) 
{   int  i, j, k, L; 
    long  ThisM; 
    for( i = 1; i <= N; i++ )   M[ i ][ i ] = 0; 
    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 ]; 
	    		if ( ThisM < M[ i ][ j ] )  /* Update min */ 
				M[ i ][ j ] = ThisM; 
			}  /* end for-L */
        }  /* end for-Left */
}


Optimal binary search tree

$T(N) = \sum p_i (1+d_i)$

All-pairs shortest path

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* A[ ] contains the adjacency matrix with A[ i ][ i ] = 0 */ 
/* D[ ] contains the values of the shortest path */ 
/* N is the number of vertices */ 
/* A negative cycle exists iff D[ i ][ i ] < 0 */ 
void AllPairs( TwoDimArray A, TwoDimArray D, int N ) 
{   int  i, j, k; 
    for ( i = 0; i < N; i++ )  /* Initialize D */ 
    	for( j = 0; j < N; j++ )
	 		D[ i ][ j ] = A[ i ][ j ]; 
    for( k = 0; k < N; k++ )  /* add one vertex k into the path */
         for( i = 0; i < N; i++ ) 
	 		for( j = 0; j < N; j++ ) 
	    		if( D[ i ][ k ] + D[ k ][ j ] < D[ i ][ j ] ) 
					/* Update shortest path */ 
					D[ i ][ j ] = D[ i ][ k ] + D[ k ][ j ]; 
}


Product assembly