动态规划
算法 

什么是动态规划算法

动态规划算法同分治方法相似，都是通过组合子问题的解来求解原问题。分治算法将原问题划分为互不相交的子问题，递归地求解问题，在再将子问题的解组合起来，求出原问题的解。而动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。在这种情况向下，分治算法会做许多不必要的计算，它会反复计算公共子问题。而动态规划算法对公共子问题只求解一次，然后将其解保存在一个表格中，避免了不必要的计算。 动态规划算法通常用来求解最优化问题。 动态规划算法的设计步骤：

  1. 刻画一个最优解的结构特征
  2. 递归地定义最优解的值
  3. 计算最优解的值，通常采用自底向上的方法
  4. 利用计算出的信息构造一个解。

动态规划原理

动态规划算法就是将递归算法重复计算子问题的计算结果保留，这样可以避免重复计算子问题。

从工程角度看，在什么情况下应该使用动态规划算法求解问题呢？

适合应用动态规划算法求解的最优化问题，应该具备两个要素：最优子结构和子问题重叠。

最优子结构

用动态规划求解最优问题的第一步就是刻画最优解的结构。**如果一个问题的最优解包含子问题的最优解，我们就称此问题具有最优子结构性质。**具有最优子结构是使用动态规划算法的标志。

发掘最优子结构性质可以采用如下通用模式：

  1. 证明问题最优解的第一个组成部分是做出一个选择，做出这个选择后会产生一个或者多个待解的子问题
  2. 给定一个问题，在其可能的第一步选择中，假定已经知道哪种选择才会得到最优解。
  3. 给定可获得的最优解后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间。
  4. 用“剪切-粘贴”的技术证明：作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。可以利用反正法：假定子问题的解不是其自身的最优解，那么我们就可以从原问题的解中“剪切”掉这些非最优解，将最优解“粘贴”进去，从而得到原问题的一个更优解，这与最初的解是原问题的最优解的前提假设矛盾。

一个刻画问题的好经验就是：保持子问题空间尽量简单，只有在必要时才扩展它。（使用几维数组保存子问题的解）。

我们可以用子问题的总数和每个子问题需要考察多少种选择这两个因素的乘积来粗略分析动态规划算法的运行时间。对于钢条切割问题，共有n个子问题，每个子问题最多需要考察n中选择，因此运行时间是 $O(n^2)$. 动态规划方法中，我们通常会自底向上地使用最优子结构，首先求解子问题的最优解，然后求解原问题的最优解。在求解原问题过程中，我们需要在涉及的子问题中做出选择，选出能得到原问题最优解的子问题。

是否是最优解

在尝试使用动态规划时要注意问题是否有最优子结构。尤其注意两个子问题是否是无关的，即同一个原问题的一个子问题的解不影响另一个子问题的解。

重叠子问题

适合动态规划方法求解的最优化问题应该具备的第二个性质是 问题的递归算法会反复地求解相同的子问题，而不是一直生成新的问题 一般来讲，不同子问题的总数是输入规模的多项式函数最好。如果递归算法反复求解相同的子问题，我们就称最优化问题具有重叠子问题性质。与之相对，适合用分治方法求解的问题通常在递归的每一步都生成全新的问题。 一个问题的自然递归算法的递归调用树中出现相同的子问题，而不同的子问题的总数很少时，动态规划算都能提高效率。

重构最优解

我们通常将每个子问题所做的选择存储在一个表里，这样就不用根据代价重构这些信息。就如钢条切割问题中的带备忘机制的递归算法。

钢条切割

钢条切割问题：给定一段长度为n英寸的钢条和一个价格表 $p_i(i=1,2,…,n)$，求钢条的切割方案，使得销售收益 $r_n$ 最大。价格表如下：

长度12345678910
价格1589101717202430

长度为$n$英寸的钢条共有 $2^{(n-1)}$ 种不同的切割方案，因为在距离钢条左端 $i$ 英寸处，可以选择切割或不切割。我们用加号表示切割方案，$7=2+2+3$ 表示将长度为7的钢条切成三段。如果最优解将钢条切割为k段($1\leq k\leq n$)，那么最优的切割方案 $$ n = i_1 + i_2 + … + i_k $$ 该方案的最大收益是 $$ r_n = p_{i1} + p_{i2} + … + p_{ik} $$ 更直接的，我们可以将钢条的最优切割收益记做： $$ r_n = \max \left(p_n, r_1 + r_{n-1}, r_2 + r_{n-2}, …, r_{n-1} + r_1\right)$$ 第一个参数 $p_n$ 对应不切割，直接出售长度为n的钢条的方案。其他n-1个参数对应另外n-1种方案：对于每个 $i=1,2…,n-1$，首先将钢条切割成长度为 $i$ 和 $n-i$ 的两段，接着求解这两段的最优切割收益 $r_i$和$r_{n-i}$，因为无法预知哪种方案会获得最优收益，我们需要考虑所有可能的i，选择其中收益最大者。 为了求解规模为n的原问题，我们先求解形式完全一样，但规模更小的子问题。即当完成首次切割以后，我们将两段钢条看成两个独立的钢条切割问题，通过组合两个相关子问题的最优解，并在所有可能的两段切割方案中选区组合收益最大者，构成原问题的解，该问题是满足最优子结构的。 我们首先使用递归方式求解该问题，其递归式可以写为： $r_n = \max (p_i + r_{n-i}) 1\leq i \leq n$ 其伪代码如下：

CUT-ROD(p,n)
    if n == 0
        return 0
    q = -∞
    for i=1 to n
        q = max(q, p[i] + CUT-ROD(p, n-i))
    return q

该算法的时间复杂度是 $2^n$。可以看到该算法反复地用相同的参数值对自身进行递归调用，即它反复地求解相同的子问题。而动态规划算法可以仔细安排求解顺序，对每个子问题都只求解一次，并将结果保持下来。如果随后需要再次使用该解，只需查询保存的结果，而不必重新计算。动态规划是用额外的存储空间来节省时间的算法，可能将一个指数时间的解转化成一个多项式时间的解。

使用动态规划方法求解最优钢条切割问题

朴素递归算法之所以效率很低，是因为它反复地求解相同的子问题。动态规划方法仔细安排求解顺序，对每个子问题只求解一次，并将结果保存下来。如果随后要在此需要子问题的解，只需要查询保存的结果，而不用重新计算。动态规划算法付出额外的内存空间来节省时间 动态规划有两种等价的实现方式：

  1. 带备忘录的自顶向下法。 此方法仍按自然的递归形式编写过程，但过程中会保存每个子问题的解（数组或散列表等）。当需要一个子问题的解时，首先检查是否已经保存过此解，从而节省计算时间。

    MEMOIZED-CUT-ROD(p, u)
    let r[0...n] be a new array
    for i=0 to n
        r[i] = -∞
    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 = -∞
        for i=1 to n
            q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n-i, r))

  2. 自底向上法。 此方法一般需要恰当定义子问题的“规模”，使得任何子问题的求解都只依赖于“更小的”子问题的解。因此我们将子问题按照规模排序，按由小到大的顺序求解。当求解某个问题时，它所依赖的那些更小的子问题都已经求解完毕，结果已经保存，每个子问题都只需要求解一次。

    BOTTOM-UP-ROD(p, n)
    let r[0...n] and s[0...n] be a new array
    n[0] = 0;
    for j=1 to n
        q = -∞
        for i=1 to j
            if q < p[i] + r[j-i]
                q =  p[i] + r[j-i]
                s[j] = i;
            r[j] = q
    return r and s

这两种方法具有渐近运行时间，由于没有频繁的递归函数调用开销，自底向上法的时间复杂度具有更小的系数。

子问题图

当考虑一个动态规划问题时，我们应该弄清楚所设计的子问题以及子问题之间的依赖关系。 问题的子问题图准确地表达了问题间的依赖关系。它是一个有向图，每个顶点唯一地对应一个子问题。若子问题x的最优解需要直接用到子问题y的最优解，那么久会在子问题图中有一条从子问题x到子问题y的顶点的有向边。 32140

子问题图 $G=(V, E)$ 的规模可以帮助我们确定动态规划算法的运行时间，由于每个子问题只求解一次，因此算法运行时间等于每个子问题求解时间之和。通常，一个子问题的求解时间与子问题图中对应顶点的度（出射边的数目）成正比，而子问题的数目等于子问题图的顶点数。因此，动态规划算法的运行时间与定点和边的数量呈线性关系。

重构解

在上述的 BOTTOM-UP-CUT-ROD 中，我们通过数组s保存了每个子问题的最优收益值。我们可以通过如下方式获取最优切割方案：

PRINT-CUT-ROD-SOLUTION (p, n)
    (r,s) = BOTTOM-UP-CUT-ROD(p,n)
    while n > 0
        print s[n]
        n = n - s[n]

最长公共子序列

子序列定义：给定一个序列 $X={x_1,x_2,…,x_m}$, 另一个序列 $Z={z_1,z_2,…z_k}$ 满足如下条件时 $Z$ 是 $X$ 的子序列，即存在一个严格递增的 $X$ 的下标序列 ${i_1,i_2,…,i_k}$, 对于所有的$j=1,2,…k$, 满足 $x_{ij}$ = $z_i$。

公共子序列：给定两个序列X和Y，如果Z既是X的子序列，也是Y的子序列，那么成Z是X和Y的公共子序列

最长子序列问题(LCS)：给定两个序列 $X={x_1,x_2,…,x_m}$ 和 $Y={y_1,y_2,…,y_n}$, 求X和Y的公共子序列.

刻画最长公共子序列特征

如果用暴力搜索方法求解LCS，就要穷举X的所有子序列，对每个子序列都要检查是否是Y的子序列，记录找到的最长子序列。X的每个子序列对应X的元素集合的一个子集，有2^m个子序列，因此暴力方法的运行时间为指数级。

但是LCS问题具有最优子结构。令Z为X和Y的任意LCS：

  1. 如果$x_m = y_n$, 则$z_k = x_m = y_n$, 且 $Z_{k-1}$ 是 $X_{m-1}$ 和 $Y_{n-1}$ 的一个LCS
  2. 如果$x_m \neq y_n$, 那么$z_k \neq x_m$, 意味着 $Z$ 是$X_{m-1}$ 和 $Y$ 的一个LCS
  3. 如果$x_m \neq y_n$, 那么$z_k \neq y_n$, 意味着 $Z$ 是 $X$ 和 $Y_{n-1}$的一个LCS

一个递归解

求解 $X$ 和 $Y$ 的一个 LCS时，我们需要求解一个或两个子问题。如果$x_m = y_n$, 我们应该求解 $X_{m-1}$ 和 $Y_{n-1}$ 的一个LCS。将$x_m = y_n$追加到这个LCS的末尾；如果$x_m \neq y_n$，我们必须求解两个子问题：$X_{m-1}$ 和 $Y$ 的一个LCS 和 $X$和 $Y_{n-1}$ 的一个LCS，两个中较长者为$X$和$Y$的一个LCS. 由于这些情况覆盖了所有可能性，因此我们知道必然有一个子问题的最优出现在$X$和$Y$的LCS中。 很容易看出LCS问题具有重叠子问题性质。 设计LCS问题的递归算法首先要建立最优解的d递归式。我们定义$c[i, j]$表示$X_i$和$Y_j$的LCS长度。根据LCS问题的最优子结构性质，可得如下公式： $$c[i,j] = \left\{ \begin{array}{ll} 0 & \textrm{if $i=0$ or $j=0$}\\ c[i-1,j-1]+1 & \textrm{if $i,j>0$ and $x_i \neq y_j$}\\ max(c[i,j-1], c[i-1,j]) & \textrm{if $i,j>0$ and $x_i \neq y_j$} \end{array} \right.$$

计算LCS的长度

根据上面的公式，我们可以很容易地写出一个指数时间的递归算法来计算两个序列的LCS的长度。但是LCS问题只有 $\Theta$ 个不同的子问题，因此，我们可以使用动态规划方法自底向上地计算。

过程LCS-LENGTH接受两个序列$X={x_1, x_2, …, x_m}$和$Y={y_1, y_2, … , y_n}$为输入。它将值保存在$c[0…m,0…n]$中，并按行主次序计算表项（即首先由左至右计算c的第一行，然后计算第二行，依此类推）。过程还维护一个表$b[1…m, 1…n]$帮助构造最优解。

LCS-LENGTH(X, Y)
    m = X.length
    n = Y.length
    let c[0...m,0...n] and b[1...m, 1...n] be new table
    for i = 1 to m
        c[i,0] = 0
    for j = 0 to n
        c[0,j] = 0
    for i = 1 to m
        for j = 1 to n
            if X[i] == Y[j]
                c[i,j] = c[i-1,j-1] + 1
                b[i,j] = "left-top"
            elseif c[i-1,j] >= c[i,j-1]
                c[i,j] = c[i-1,j]
                b[i,j] = "top"
            elseif
                b[i,j] = "left"
    return c and b

构造LCS

我们可以用LCS-LENGTH返回的b快速构造X和Y的LCS，只需从$b[m,n]$开始，按位置追踪下去即可

PRINT-LCS(b, X, i, j)
    if i == 0 or j == 0
        return
    if b[i,j] == "left-top"
        PRINT-LCS(b,X, i-1, j-1)
        print X[i]
    elseif b[i,j] == "top"
        PRINT-LCS(b, X, i-1, j)
    else PRINT-LCS(b, X, i, j-1)

算法改进

一旦设计出一个算法，通常情况下都会有在时空开销上有改进的余地。对LCS算法，可以完全去掉表b，每个$c[i,j]$项只依赖于表c中的其他三项：$c[i-1,j], c[i,j-1],c[i-1,j-1]$，我们可以在$O(1)$的时间根据$c[i,j]$判断出使用了三项中的哪一项

最优二叉搜索树

最优二叉搜索树 的形式化定义如下： 给定一个n个不同关键字的已排序的序列$K=\langle k_1,k_2, …, k_n \rangle$(因此$k_1<k_2<…<k_n$)，对每个关键字$k_i$，都有一个概率$p_i$表示其搜索频率。有些要搜索的值可能不在$K$中，因此还有$n+1$个“伪关键字”$d_0, d_1, …, d_n$表示不在$K$中的值。$d_0$表示所有小于$k_1$的值，$d_n$表示所有大于$k_n$的值，对$i=1,2,…,n-1$，伪关键字$d_i$表示所有在$k_i$和$k_{i+1}$之间的值。对每个伪关键字$d_i$，也都有一个概率$p_i$表示对应的搜索频率。 那么最优二叉搜索树是指对于给定的集合我们希望构造一棵期望搜索代价最小的二叉搜索树。

知道每个关键字和伪关键字的搜索概率，因而可以确定在一棵给定的二叉搜索树$T$中进行一次搜索的期望代价。假定一次搜索的代价等于访问的结点数，即此次搜索找到的结点在$T$中的深度再加1，那么在$T$中一次搜索的代价期望为: $$E[T]=\sum_{i=1}^n(depth_T(k_i)+1)\cdot p_i + \sum_{i=0}^n(depth_T(d_i)+1)\cdot q_i=1+\sum_{i=1}^ndepth_T(k_i)\cdot p_i + \sum_{i=0}^ndepth_T(d_i)\cdot q_i$$

最优二叉树的结构

如果一棵最优二叉搜索要$T$有一棵包含关键字$k_i, … k_j$的子树$T_1$ ，那么T必然包含关键字$k_i, … k_j$和伪关键字$d_{i-1}, … d_j$的子问题的最优解。可以用剪切——粘贴法来证明：如果存在子树$T_2$，其期望搜索代价比$T_1$低，那么我们将$T_1$从$T$中删除，将$T_2$粘贴到相应位置，从而得到一棵期望搜索代价低于$T$的二叉搜索树，与$T$最优假设矛盾。

一个递归算法

选取子问题域为：求解包含关键字$k_i, … k_j$的最优二叉搜索树，其中$i\ge 1, j\le n$且$j\ge i-1$，定义$e[i,j]$为在包含关键字$k_i, … k_j$的最优二叉搜索树中进行一次搜索的期望代价。最终，希望计算出$e[1,n]$.

$j=i-1$的情况最为简单，由于子树只包含伪关键字 $d_{i-1}$，期望搜索代价为$e[i,i-1]=q_{i-1}$. 当$j\geq i$时，需要从$k_i,…,k_j$中选择一个根结点 $k_r$，然后构造一棵包含关键字$k_i,…,k_{r-1}$的最优二叉搜索树作为其左子树，以及一想要包含关键字$k_{r+1},…,k_j$的二叉搜索树作为其右子树。由于每个结点的深度都增加了1，这棵子树的期望搜索代价的增加值应为所有概率之和。对于包含关键字$k_i,…,k_j$的子树，所有概率之和为 $$\omega(i,j)=\sum_{l=i}^j{p_l} + \sum_{l=i-1}^j{q_i}$$

因此，若$k_r$为包含关键字$k_i,…,k_j$的最优二叉搜索树的根结点，有如下公式： $$e[i,j] = p_r + (e[i,r-1] + \omega(i,r-1)) + (e[r+1,j] + \omega(r+1,j))$$ 根据 $\omega(i,j)=\omega(i,r-1)+p_r+\omega(r+1,j)$ ，有： $$e[i,j]=e[i,r-1]+e[r+1,j]+\omega(i,j)$$

最终递归公式为： $$e[i,j]=\left\{ \begin{array}{ll} q_{i-1}& \textrm{if $j=i-1$}\\ \min_{i\le r\le j}(e[i,r-1]+e[r+1,j]+\omega(i,j)) & \textrm{if $i\le j$} \end{array} \right. $$

计算最优二叉树搜索的期望搜索代价

二叉搜索树的子问题是由连续的下标子域组成。其伪代码如下：

OPTIMAL-BST(p, q, n)
    let e[1..n+1,0..n], w[1..n+1,0..n], root[1..n,1..n] be new tables
    for i=1 to n+1
        e[i,i-1] = q[i-1]
        w[i,i-1] = q[i-1]
    for l=1 to n
        for i = 1 to n-l+1
            j = i+l-1
            e[i,j] = ∞
            w[i,j] = w[i,j-1] + p[j] + q[j]
            for r=i to j
                t = e[i,r-1] + e[r+1,j] + w[i,j]
                if t < e[i,j]
                    e[i,j] = t
                    root[i,j] = r
    return e and root
  • other thing
local_offer #算法 
navigate_before navigate_next