Chapter 3 动态规划

最优子结构性质重叠子问题性质 (期末一章一个大题，就这么问)

矩阵连乘、最长公共子序列、最大子段和、背包最优质、极大极小、全局最优

引言

使用动态规划可以优化分治算法解决Fabonacci数列的问题。分治算法的时间复杂度为O(2^n)，而动态规划通过保存中间结果将时间复杂度降低到O(n)。

零、矩阵连乘问题

矩阵连乘问题是指给定一系列矩阵，求它们的最优乘法顺序，以使得计算所需的标量乘法次数最少。设有n个矩阵A1, A2, …, An，矩阵Ai的维数为pi-1 × pi。定义一个n维数组dp，其中dp[i][j]表示矩阵Ai到Aj的最优乘法次数。

2 动态规划解法

2.1 递归结构

$$dp[i][j] = \begin{cases} 0 & , i = j \\ \min_{i \leq k < j} \{dp[i][k] + dp[k+1][j] + p_{i-1}p_kp_j\} & , i < j \end{cases}$$

2.2 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


void MatrixChainOrder(int p[], int n){
    int dp[n][n];
    for(int i = 1; i < n; i++) dp[i][i] = 0;

    for(int l = 2; l < n; l++){ // l is chain length
        for(int i = 1; i < n - l + 1; i++){
            int j = i + l - 1;
            dp[i][j] = INT_MAX;
            for(int k = i; k <= j - 1; k++){
                int q = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j];
                if(q < dp[i][j]) dp[i][j] = q;
            }
        }
    }
}

复杂度分析：时间复杂度为$O(n^{3})$，空间复杂度为$O(n^{2})$。

一、凸多边形最优三角剖分

偷来的图凸n边形的三角剖分与n-1个叶子的语法树之间存在一一对应关系。由于n个矩阵的完全加括号乘积与n个叶子的语法树之间存在一一对应关系，因此n个矩阵的完全加括号乘积也与凸(n+1)边形的三角剖分之间存在一一对应关系。事实上，矩阵连乘积的最优计算次序问题是凸多边形最优三角剖分问题的一个特殊情形。对于给定的矩阵链A1A2..An，定义一个与之相应的凸(n+1)边形P={v0 ,v1 ,… ,vn}，使得矩阵Ai与凸多边形的边vi-1vi一一对应。若矩阵Ai的维数为pi-1×pi,i=1,2,…,n，则定义三角形vivjvk上的权函数值为： ω(vivjvk)=pipjpk。依此权函数的定义，凸多边形P的最优三角剖分所对应的语法树给出矩阵链A1A2..An的最优完全加括号方式。

1 最优子结构性质

2 递归结构

二、最大子段和

最大子段和问题是指在一个给定的一维数列中，找出一个连续子段，使得该子段的元素和最大。

1 分治解法

2 动态规划解法

2.1 递归结构

$$dp[i] = \max_{0 \leq j \leq i} \left\{ \sum_{k=j}^{i} a[k] \right\} \quad i \leq n$$$$dp[i] = \begin{cases} a[i] + dp[i-1] & , dp[i-1] > 0 \\ a[i] & , dp[i-1] \leq 0 \end{cases}$$$$rec[i] = \begin{cases} rec[i-1] & , dp[i-1] > 0 \\ i & , dp[i-1] \leq 0 \end{cases}$$

2.2 代码（从前向后）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


void MAXSUB(int a[], int n){
    int *b = new int[MAX];
    int *rec = new int[max];
    b[0] = a[0];
    rec[0] = 0;

    int max = b[0];
    
    for(int i = 1; i < n; i++){
        if(b[i-1] > 0) {
            b[i] = b[i-1] + a[i];
            rec = rec[i-1];
        }
        else{
            b[i] = a[i];
            rec = i;
        }
        if(b[i] > max) max = b[i];
    }
}

三、最长公共子序列

1 递归结构

设有两个序列X=x1,x2,…,xm和Y=y1,y2,…,yn，定义X的前i个元素组成的序列为Xi=x1,x2,…,xi，Y的前j个元素组成的序列为Yj=y1,y2,…,yj。设LCS[i][j]表示序列Xi和Yj的最长公共子序列的长度，则有如下递归关系：

$$ LCS[i][j] = \begin{cases} LCS[i-1][j-1] + 1 & , X[i] = Y[j] \\ \max(LCS[i-1][j], LCS[i][j-1]) & , X[i] \neq Y[j] \end{cases} $$

2 动态规划解法

2.1 递归结构

$$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & , X[i] = Y[j] \\ \max(dp[i-1][j], dp[i][j-1]) & , X[i] \neq Y[j] \end{cases}$$

2.2 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


void LCS(char X[], char Y[], int m, int n){
    int dp[m+1][n+1];
    for(int i = 0; i <= m; i++) dp[i][0] = 0;
    for(int j = 0; j <= n; j++) dp[0][j] = 0;

    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(X[i-1] == Y[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            else{
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
}

四、0-1背包问题

1 递归结构

设有n件物品和一个容量为W的背包。每件物品i有一个重量wi和一个价值vi。定义dp[i][j]表示前i件物品在背包容量为j时的最大价值，则有如下递归关系：

$$ dp[i][j] = \begin{cases} dp[i-1][j] & , j < w_i \\ \max(dp[i-1][j], dp[i-1][j-w_i] + v_i) & , j \geq w_i \end{cases} $$

2 动态规划解法

2.1 递归结构

$$dp[i][j] = \begin{cases} dp[i-1][j] & , j < w_i \\ \max(dp[i-1][j], dp[i-1][j-w_i] + v_i) & , j \geq w_i \end{cases} $$$$dp[0][j] = 0, \quad 0 \leq j \leq W$$

2.2 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


void Knapsack(int w[], int v[], int n, int W){
    int dp[n+1][W+1];
    for(int i = 0; i <= n; i++) dp[i][0] = 0;
    for(int j = 0; j <= W; j++) dp[0][j] = 0;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= W; j++){
            if(j < w[i-1]){
                dp[i][j] = dp[i-1][j];
            }
            else{
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
            }
        }
    }
}