Lesson8：动态规划

对于一个能用动态规划解决的问题，一般采用如下思路解决：

1. 将原问题划分为若干阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为状态）；
2. 寻找每一个状态的可能决策，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程）。
3. 按顺序求解每一个阶段的问题。

状态表达子问题，状态转移方程用于实现子问题的递推关系。

动态规划要把子问题给储存起来。

矩阵乘法：

想象一下N个矩阵相乘

最下方的状态转移方程，是基于最后阶段两个矩阵相乘的状态。

最优子结构：一个问题的最优解包含其子问题的最优解，与子问题的次优解之类的都无关

可以看到，在这一问题中，困难与重点都在于状态/子问题的确定。

伪代码:

/* 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 */
}

词语搜索树

F[i][N] = F[i][K-i] + f[k+1][N-K+i-1] + P_k + P_i:k-1 + P_k+1:i+N

后面又加一遍P_i:k-1 + P_k+1:i+N的原因是子树向下了一层，所以需要累加。