跳转至

Dynamic Programming

约 490 个字 55 行代码 8 张图片 预计阅读时间 4 分钟

  • DP 常用于解决 最优化问题 和计数问题。
  • 一般而言，用 DP 解决的问题需要具有以下特征：
    • 最优子结构
    • 无后效性
  • 用空间换时间，我们常常需要一个状态值表示对于当前状态的答案（可能是截至当前状态）

Fibonacci Numbers

\[F(N) = F(N-1) + F(N-2)\]
C
1
2
3
4
5
6
int Fib(int N) {
    if(N <= 1)
        return 1;
    else
        return Fib(N-1) + Fib(N-2);
}
\[ T(N) \geq T(N-1) + T(N-2) \]

alt text

  • 问题：我们多次计算了相同的子问题，产生了很多额外的开销。
  • 解决：从底向上，答案等于当前结果和前一个答案之和。

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int Fib(int N) {
    int i, Last, NextToLast, answer;
    if(N<=1) {
        return 1;
    }
    Last = NextToLast = 1;
    for (i = 0; i < N; i++) {
        answer = Last + NextToLast;
        NextToLast = Last;
        Last = answer;
    }
    return answer;
}
$$ T(N) = O(N) $$

Ordering Matrix Multiplications

矩阵具有结合律，通过不同的组合会有不同的时间开销。

令\(b_n\) = number of different ways to compute \(M_1\), \(M_2\), \(···\), \(M_n\) 我们有\(b_2 = 1, b_3 = 2, b_4 = 5, \cdots\).令\(M_i\)是\(r_{i-1} \times r_i\)矩阵，\(M_{ij} = M_i \cdots M_j\).那么\(M_{1n} = M_1 \cdots M_n = M_{1i} \cdot M_{i+1 n}\)

所以\(b_n = \sum_{i=1}^{n-1} b_i b_{n-i}\)

\[b_n = O(\frac{4^n}{n\sqrt{n}})\]

alt text

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
void OptMatrix(const long r[], int N, TwoDimArray M) {
    int i, j, k, L;
    long thisM;
    fot (i = 1; i < N; i++) {
        M[i][i] = 0;
    }

    for(k = 1; k < N; k++) {
        for(i = 0; i <= N-k; i++) {
            j = i + k;
            M[i][j] = INF;
            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]) {
                    M[i][j] = thisM;
                }
            }
        }
    }
}
\[ T(N) = O(N^3) \]

Optimal Binary Search Tree

alt text

选根就行。下面是选根（每一个子问题）的具体操作。

alt text

最终三种树的cost：

alt text

All Pairs Shortest Path

  • Method 1 (Dijkstra算法)

循环调用dijkstra算法。\(T(N) = O(|V|^3)\)

  • Method 2 (Floyd算法)

定义 \(D^k[i][j]\) = min{length of path i -> {l <= k} -> j} 和 \(D^{-1}[i][j]\) = \(Cost[i][j]\)。

上标 k 是指从 i 到 j 的路径可以经过编号为 0 到 k 的节点。

我们定义子问题，能得到如下式子：

\[ D^k[i][j] = \min \{ D^{k-1}[i][j], D^{k-1}[i][k] + D^{k-1}[k][j] \}, \quad k \geq 0 \]

初始状态是\(D^{-1}[i][j]\)，最终状态是\(D^{N-1}[i][j]\)。

C
 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]; 
}

Floyd算法的时间复杂度为：

\[ T(N) = O(N^3) \]

但是在稠密图中速度更快。

Product Assembly

  • Two assembly lines for the same car
  • Different technology (time) for each stage
  • One can change lines between stages
  • Minimize the total assembly time

alt text

  • Exhaustive search gives \(O( 2^N )\) time + \(O( N )\) space

为什么决定用动态规划？

alt text

alt text