跳转至

8 Dynamic Programming

文本统计：约 818 个字 • 37 行代码

8.1 Ordering Matrix Multiplication

一系列矩阵相乘选择合理的顺序可以减小计算量

Suppose we are to multiply n matrices \(M_1\times \cdots \times M_n\) where \(M_i\) is an \(r_{i-1}\times r_i\) matrix. Let \(m_{ij}\) be the cost of the optimal way to compute \(M_i\times \cdots \times M_j\) . Then we have the recurrence equations:

\[ m_{ij}=\left\{ \begin{aligned} &0&&\text{if}\ i=j\\ &min_{i\le l\le j}\{m_{il}+m_{l+1j}+r_{i-1}r_lr_j\}&&\text{if}\ j>i \end{aligned}\right. \]
/* 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 */
}

时间复杂度为 \(T(N)=O(N^3)\)

8.2 Optimal Binary Search Tree

Given \(N\) words \(w_1 < w_2 < …… < w_N\), and the probability of searching for each \(w_i\) is \(p_i\) . Arrange these words in a binary search tree in a way that minimize the expected total access time.

这N个单词是按照中序排列的，寻找最小的访问时间只需要选择根节点然后分裂为两个子问题就行了

Example

转移方程为

\[ c_{i,j}=\min_{i\le l\le j}\{w_{i,j}+c_{i,l-1}+c_{l+1,j}\} \]

其中 \(c_{i,j}\) 就是从第 \(i\) 个 word 到第 \(j\) 个word 的最佳结果，\(w_{i,j}\) 则是权值之和

8.3 All-Pairs Shortest Path

For all pairs of \(v_i\) and \(v_j\) ( \(i \ne j\) ), find the shortest path between.

法1：使用单源的最小路径算法，使用V次

  • Dijkstra \(O(VE+V^2\lg V)\)
  • BellmanFord \(O(V^2E)\)

法2：Floyd - Warshell 算法

定义：\(D^k[i][j]=\min\{\text{length of path } i\rightarrow\{l\le k\}\rightarrow j\}\) 记 \(D^{-1}[i][j]=\text{Cost}[i][j]\)

Then the length of the shortest path from \(i\) to \(j\) is \(D^{|V|-1}[i][j]\)

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

算法复杂度：\(O(|V|^3)\)

8.4 Product Assembly

有两条流水线来组装汽车，拥有相同的步骤，但两条组装线会分别花不同的时间。你可以在两条线之间反复游走，但跳转需要时间，请找到最快路径

思路很简单，只需要依次算出到达各个点的最快时间，计算下一个最快时间的时候只需要考虑上一个跳转还是没跳转的情况，并列出相应的递推式。

8.5 Find the longest palindrome

A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples: civic, racecar, and aibohphobia (fear of palindromes).

Give an efficient algorithm to find the longest palindrome that is a subsequence of a given input string. For example, given the input character, your algorithm should return carac.

Notice the subsequence does not have to be consecutive.

定义：

\(L(i,j)\)表示在字符串\(X\)中从位置\(i\)到位置\(j\)（包括\(i\)和\(j\)）之间的最长回文子序列的长度。

递推关系：

对于任意的i<j，我们有以下两种情况：

  • 如果\(X[i]\)和\(X[j]\)相等：

  • 如果\(j\)和\(i\)相邻（即\(j=i+1\)），那么这两个字符本身就是长度为2的回文串：

\[ L(i,j)=2 \]
  • 否则，如果\(j\)和\(i\)不相邻，那么可以在i和j之间的最长回文子序列基础上加上这两个字符：
\[ L(i,j)=L(i+1,j−1)+2 \]
  • 如果\(X[i]\)和\(X[j]\)不等，则最长回文子序列要么包含\(X[j]\)而不包含\(X[i]\)，要么包含\(X[i]\)而不包含\(X[j]\)。因此，最长回文子序列的长度是两者中的较大值：
\[ L(i,j)=max(L(i+1,j),L(i,j−1)) \]

总结：

\[ L(i,j)= \begin{cases} 1&\text{if }i=j\\ 2&\text{if }i=j−1\text{ and }X[i]=X[j]\\ L(i+1,j−1)+2&\text{if }X[i]=X[j]\text{ and }j≠i+1\\ \max(L(i+1,j),L(i,j−1))&\text{otherwise} \end{cases} \]

评论区

对你有帮助的话请给我个赞和 star => GitHub stars
欢迎跟我探讨！！！