《算法导论》:动态规划学习笔记-蒲公英云

参考资料：《算法导论》

动态规划方法

动态规划方法用于解决这样一类问题:

问题具有最优子结构性质，即如果这个问题达到了最优解，那么此时构成它的子问题也应当是最优解, 这与贪心算法类似
子问题空间应该足够”小”, 即问题的递归算法会反复求解相同的子问题，而不是一直生成新的子问题
可能需要尝试不同的划分方法，将问题分解成不同的子问题，以求得全局最优解

一般求解步骤:

刻画一个最优解的结构特征
递归地定义最优解的值
通常采用自底向上的方法计算最优解的值
构造最优解

问题求解

这里记录了书上提到的三个例子

钢条切割问题展示了动态规划中等价的两种实现
- 带备忘的自顶向下
- 自底向上
矩阵链乘法和最长公共子序列展示了动态规划问题的一般分析方法

1.钢条切割问题

一个长度为n的钢条，n为整数，切割为多个长度仍为整数的子钢条，每种长度的钢条价格不一，有一个记录每种长度的钢条价格的价格表p, 求最优切割方案
由条件可以推导出以下结论

如果长度为n的钢条价格足够高，则无需切割
共有 2 n − 1 2^{n-1} 2n−1种不同的切割方案，切割数目m从0到n，每种数目对应 C n − 1 m C_{n-1}^m Cn−1m种方法，求和得 2 n − 1 2^{n-1} 2n−1

递归实现

思路: 将钢条在下标 i i i处分为左右两部分，(因为总会有一个分割点，不切割的话 i i i=0) ，那么可以只对右边长度为 n − i n-i n−i的部分进行递归处理，若用 f ( n ) f(n) f(n)表示长度为 n n n的钢条的最佳切割方案，则有:
f ( n ) = m a x ( p i + f ( n − i ) ) 0 < = i < = n f(n) = max(p_i+f(n-i)) _{0<=i<=n} f(n)=max(pi+f(n−i))0<=i<=n
时间复杂度: 由于有 2 n − 1 2^{n-1} 2n−1种分法，递归的解法实际上尝试了所有的分法，所以时间复杂度: O ( 2 n − 1 ) O(2^{n-1}) O(2n−1)
在这里插入图片描述

分析: 递归的解法之所以慢，是因为在递归时重复求解了子问题，如果使用一个表记录子问题的结果，就可以提升求解效率

动态规划方法实现

1.自顶向下
数组r保存了从0到n每个长度的最优方案，以确保不会重复计算。本例中这种方法分析起来不如自底向上清晰

MEMOIZED-CUT-ROD(p,n)
let r[0...n] be a new array
for i=0 to n:
    r[i] = INT_MIN
return MEMOIZED-CUT-ROD-AUX(p,n,r)
MEMOIZED-CUT-ROD-AUX(p,n,r)
if r[n] >= 0:
    return r[n]
if n == 0:
    q = 0
else:
    q = MIN
    for i=1 to n:
        q = max(q,p[i]+MEMOIZED-CUT-ROD-AUX(p,n-i,r))
r[n]=q
return q

在这里插入图片描述
2.自底向上
自底向上方法同样使用数组r保存从0到n每个长度的最优方案，思路是一样的，但是结构更清晰，上一个方法由于使用了递归，分析起来比较麻烦。

BOTTOM-UP-CUT-ROD(p, n)
let r[0...n] be a new array
r[0]=0
for j=1 to n:
    q = MIN
    for i=1 to j:
        q=max(q,p[i]+r[j-i])
    r[j]=q
return r[n]

在这里插入图片描述

2.矩阵链乘法

在这里插入图片描述

步骤1: 最优方案的结构特征

一个 m ∗ n m*n m∗n的矩阵和一个 n ∗ k n*k n∗k的矩阵相乘，需要进行 m n k mnk mnk次乘法运算
假设存在最优划分点k, 那么k的左右两边都是最优划分的

步骤2: 递归求解方案

若用 m [ i , j ] m[i, j] m[i,j]表示计算 A i . . . A j A_i…A_j Ai…Aj的最优解，那么在 i i i与 j j j范围内寻找一个k, 假设这个k是计算 A i . . . A j A_i…A_j Ai…Aj的最优划分，那么就把问题再次分解成了更小的子问题，且存在下面的递推关系，使用自底向上就可以完成求解
在这里插入图片描述

步骤3: 计算最优代价

输入是一个序列 p = < p 0 , p 1 , p 2 , . . . , p n > p= p=
使用辅助表 m [ 1… n , 1… n ] m[1…n,1…n] m[1…n,1…n] 保存代价 m [ i , j ] m[i,j] m[i,j]
另一个辅助表 s [ 1… n − 1 , 2… n ] s[1…n-1,2…n] s[1…n−1,2…n] 记录最优值 m [ i , j ] m[i,j] m[i,j]对应的分割点k

MATRIX-CHAIN-ORDER(p)
n = p.length - 1
let m[1...n, 1...n] and s[1...n-1, 2...n] be new tables
for i = 1 to n:
    m[i,i] = 0   // 当长度为0时代价为0
for l = 2 to n:  // l是子链的长度
    for i = 1 to n-l+1:
        j = i + l -1
        m[i,j] = MAX
        for k = i to j-1:
            q = m[i, k] + m[k+1,j] + p[i-1]*p[k]*p[j]
            if q < m[i, j]:
                m[i, j] = q
                s[i, j] = k

在这里插入图片描述

从长度为1、2的子链代价开始计算，逐步推导出完整的代价辅助表m

步骤4: 构造最优解

PRINT-OPTIMAL-PARENS(s, i , j)
if i==j:
    print "A[i]"
else:
    print "("
    PRINT-OPTIMAL-PARENS(s, i, s[i,j])
    PRINT-OPTIMAL-PARENS(s, s[i,j]+1,j)
    print ")"

3.最长公共子序列

子序列: 从原序列的下标集合中选取一部分递增的下标序列，以此构建的子序列
公共子序列: X和Y存在相同的子序列Z
注意点: 这里的子序列未必是原序列中连续的一部分

在这里插入图片描述

步骤1:最长公共子序列特征刻画

在这里插入图片描述

步骤2:递归解

在这里插入图片描述

步骤3: 计算LCS长度

LCS-LENGTH(X, Y)
m = X.length
n = Y.length
let b[1...m,1...n] and c[0...m,0...n] be new tables
for i = 1 to m:
    c[i, 0] = 0
for j = 1 to n:
    c[0,j] = 0
for i = 1 to n:
    for j = 1 to m:
        if x[i] == y[j]:
            c[i,j] = c[i-1,j-1] + 1
            b[i,j] = "\"
        elseif c[i-1,j] >= c[i, j-1]:
            c[i,j] = c[i-1,j]
            b[i,j] = "|"
        else:
            c[i,j] = c[i,j-1]
            b[i,j] = "--"
return c, b

b 的作用是辅助打印出LCS

步骤4: 构造LCS

PRINT-LCS(b,X,i,j)
if i==0 or j==0:
    return None
if b[i, j] == "\":
    PRINT-LCS(b,X,i-1,j-1)
    print x[i]
elseif b[i,j] == "|":
    PRINT-LCS(b,X,i-1,j)
else:
    PRINT-LCS(b,X,i,j-1)