[数据结构和算法]《算法导论》动态规划笔记(2)

上一次介绍了动态规划解决钢条切割问题，这次介绍一下动态规划的原理，什么样的最优化问题适合用动态规划解决？ 具有的两个基本特征：最优子结构和子问题重叠。

最优子结构

如果一个问题的最优解包含其子问题的最优解，称此问题具有最优子结构性质。

最优子结构发现过程：

1. 证明问题最优解的第一个组成部分是做出一个选择。

2. 对于一个给定问题，在其可能的第一步选择中，假定已经知道那种选择才会得到最优解。

3. 给定可获得最优解的选择后，你确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间。

4. 利用“剪切-粘贴”的技术证明：作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。

刻画子问题空间的经验是：保持子问题空间尽可能简单，只在必要时才扩展它。对于不同的最优化问题，最优子结构的区别在于1,原问题的最优解涉及多少个子问题以及在确定最优解使用那些子问题时，我们需要考察多少种选择。

在动态规划中，我们通常自底向上地使用最优子结构，底指的是子问题的最优解，向上指的是求原问题最优解的过程。在求解原问题解的过程中，我们需要在涉及子问题中做出选择，选出能得到原问题最优解的子问题。原问题最优解的代价通常就是子问题最优解的代价加上由此选择直接产生的代价。

以上就是最优子结构的内容，可能理解子问题和原问题之间的关系有点绕，需要仔细理解一下。然后看下重叠子问题

重叠子问题

重叠子问题是指子问题的空间必须足够小，即问题的递归算法会反复求解相同的子问题，而不是一直生成新的子问题。动态规划就是利用了这个性质，对每个子问题只求解一次，将解存入一个表中，当再次需要这个子问题时直接查表，每次查表的时间代价为常量时间。

利用动态规划求解最长公共子序列

定义：给定一个序列X=<x1, x2, x3, ..., xm>，另一个序列Z=<z1, z2, z3, ..., zk>，即存在一个严格递增的X的下标序列<i1, i2, ..., ik>，对所有的j=1， 2， 3， 。。。， k. 满足xij=zj.给定两个序列X和Y，如果Z即是X的子序列，又是Y的子序列，则Z是X和Y的公共子序列。注意这里并不一定要求连续的序列，只要是按下标顺序递增的序列即可。

下面看下如何用动态规划求解这个问题。

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

首先可以想到的是暴力搜索方法，暴力搜索就是说把X中的所有子序列找出来，然后判断是不是Y的子序列，如果是，就保存下来。对于一个有m个元素的序列，子序列一共有2的m次方种可能，时间复杂度为O（2^m），对于较长序列不适用。

定理：最长公共子序列问题的最优子结构: 两个序列的LSC包含两个序列的前缀的LCS。因此LCS问题具有最优子结构性质。前缀的意思可以理解为前i个元素。

步骤2：一个递归解

在求X=<x1, x2, ..., xm>和Y=<y1, y2, ..., yn>的一个LCS时，如果xm=yn，我们应该求解Xm-1和Yn-1的一个LCS，将xm和yn追加到这个LCS后面。如果xm不等于yn，则要求解两个子问题，求Xm-1和Y的一个LCS与X和Yn-1的一个LCS。两个LCS较长者就是最终的LCS。

由此可以看出来LCS问题的解可以通过求解子问题得到最终的LCS，也就是具有重叠子问题的性质。

步骤3：计算LCS的长度

接受两个序列X，Y为输入，首先新建一个表c，然后把结果保存到表中。表b用来帮助构造最优解，b[i,j]保存的是子问题的最优解。

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 = 0 to n

        c[0, j] = 0

for i = 1 to m

        for j = 1 to n

                if xi == yj

                        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 and b

 步骤4：构造LCS

下面的伪代码是打印构造的LCS。

PRINT-LCS（b, X, i, j）

if i == 0 or j == 0

    return

if b[i, j] == "左上箭头"

     PRINT-LCS(b, X, i-1, j-1)

      print xi

elseif b[i, j] == "向上箭头"

    PRINT-LCS(b, X, i-1,j)

else PRINT-LCS(b, X, i, j - 1)

动态规划就到这里了，主要介绍了动态规划求解的两个条件，一个是最优子结构，一个是重叠子问题，满足这两个特点的最优化问题，就可以用动态规划来求解。

最后这首歌送给正在求职的毕业生们，感觉十分符合我这几天的感受，希望大家都能找到一个好工作。 只是想吐槽一下，qq音乐居然没有原唱的。。。