第四部分 高级设计和分析技术
第十五章 动态规划
1、基本概念

　　动态规划是通过组合子问题的解而解决整个问题的，通过将问题分解为相互不独立（各个子问题包含有公共的子问题，也叫重叠子问题）的子问题，对每个子问题求解一次，将其结果保存到一张辅助表中，避免每次遇到各个子问题时重新计算。动态规划通常用于解决最优化问题，其设计步骤如下：

（1）描述最优解的结构。

（2）递归定义最优解的值。

（3）按自底向上的方式计算最优解的值。

（4）由计算出的结果构造出一个最优解。

　　第一步是选择问题的在什么时候会出现最优解，通过分析子问题的最优解而达到整个问题的最优解。在第二步，根据第一步得到的最优解描述，将整个问题分成小问题，直到问题不可再分为止，层层选择最优，构成整个问题的最优解，给出最优解的递归公式。第三步根据第二步给的递归公式，采用自底向上的策略，计算每个问题的最优解，并将结果保存到辅助表中。第四步骤是根据第三步中的最优解，借助保存在表中的值，给出最优解的构造过程。

动态规划与分治法之间的区别：
（1） 分治法是指将问题分成一些独立的子问题，递归的求解各子问题。
（2） 动态规划适用于这些子问题不是独立的情况，也就是各子问题包含公共子问题。

2、动态规划基础

　　什么时候可以使用动态规范方法解决问题呢？这个问题需要讨论一下，书中给出了采用动态规范方法的最优化问题中的两个要素：最优子结构和重叠子结构。

1）最优子结构

　　最优子结构是指问题的一个最优解中包含了其子问题的最优解。在动态规划中，每次采用子问题的最优解来构造问题的一个最优解。寻找最优子结构，遵循的共同的模式：

（1）问题的一个解可以是做一个选择，得到一个或者多个有待解决的子问题。

（2）假设对一个给定的问题，已知的是一个可以导致最优解的选择，不必关心如何确定这个选择。

（3）在已知这个选择后，要确定哪些子问题会随之发生，如何最好地描述所得到的子问题空间。

（4）利用“剪贴”技术，来证明问题的一个最优解中，使用的子问题的解本身也是最优的。

最优子结构在问题域中以两种方式变化：

（1）有多少个子问题被使用在原问题的一个最优解中。

（2）在决定一个最优解中使用哪些子问题时有多少个选择。

　　动态规划按照自底向上的策略利用最优子结构，即：首先找到子问题的最优解，解决子问题，然后逐步向上找到问题的一个最优解。为了描述子问题空间，可以遵循这样一条有效的经验规则，就是尽量保持这个空间简单，然后在需要时再扩充它。

注意：在不能应用最优子结构的时候，就一定不能假设它能够应用。 警惕使用动态规划去解决缺乏最优子结构的问题！

使用动态规划时，子问题之间必须是相互独立的！可以这样理解，N个子问题域互不相干，属于完全不同的空间。

2）重叠子问题

　　用来解决原问题的递归算法可以反复地解同样的子问题，而不是总是产生新的子问题。重叠子问题是指当一个递归算法不断地调用同一个问题。动态规划算法总是充分利用重叠子问题，通过每个子问题只解一次，把解保存在一个需要时就可以查看的表中，每次查表的时间为常数。

　　由计算出的结果反向构造一个最优解：把动态规划或者是递归过程中作出的每一次选择（记住：保存的是每次作出的选择）都保存下来，在最后就一定可以通过这些保存的选择来反向构造出最优解。
　　做备忘录的递归方法：这种方法是动态规划的一个变形，它本质上与动态规划是一样的，但是比动态规划更好理解！
　　（1） 使用普通的递归结构，自上而下的解决问题。
　　（2） 当在递归算法的执行中每一次遇到一个子问题时，就计算它的解并填入一个表中。以后每次遇到该子问题时，只要查看并返回表中先前填入的值即可。

3、总结

　　动态规划的核心就是找到问题的最优子结构，在找到最优子结构之后的消除重复子问题。最终无论是采用动态规划的自底向上的递推，还是备忘录，或者是备忘录的变型，都可以轻松的找出最优解的构造过程。

第十六章 贪心算法
贪心算法在每一步都做出当时看起来最佳的选择，它总是做出局部最优的选择，寄希望这样的选择能导致全局最优解。

  1. 活动选择问题
    有一个需要使用每个资源的n个活动组成的集合S= {a1，a2，···，an }，资源每次只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi，且 0≤ si < fi <∞ 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，则称ai和aj两个活动是兼容的。该问题就是要找出一个由互相兼容的活动组成的最大子集。例如下图所示的活动集合S，其中各项活动按照结束时间单调递增排序。
    
    从图中可以看出S***有11个活动，最大的相互兼容的活动子集为:{a1，a4，a8，a11，}和{a2，a4，a9，a11}。

递归贪心算法
贪心算法通常采用自顶向下的设计，因为不需要做出过多的选择而求解所有的子问题。
Recursive-Activity-Selector(s, f, k, n)
m = k + 1

// find the first activity in Sk to finish
while m <= n and s[m] < f[k]
m = m + 1

if m <= n
return {am} U Recursive-Activity-Selector(s, f, m, n)
else
return Ø

迭代贪心算法

1
1
Greedy-Activity-Selector(s, f)
n = s.length
A = {a1}
k = 1
for m = 2 to n
if s[m] >= f[k]
A = A U {am}
k = m
return A
2. 贪心算法原理
贪心选择性质
第一个关键要素是该性质：我们可以通过做出局部最优（贪心）选择来构造全局最优解。换句话说，当进行选择时，我们直接做出在当前问题中看来最优的选择，而不必考虑子问题的解。
在动态规划方法中，每个步骤都要进行一次选择，但选择通过依赖于子问题的解。因此，我们通常以一种自底向上的方式来解动态规划问题，先求解较小的子问题，然后是较大的子问题。
贪心算法中，总是做出当时看来最佳的选择，然后求解剩下的唯一的子问题。

最优子结构
如果一个问题的最优解包含其子问题的最优解，是称此问题具有最优子结构性质。当应用于贪心算法时，我们通常使用更为直接的最优子结构。我们可以假定，通过对原问题应用贪心选择即可得到子问题。我们真正要做的全部工作就是论证：将子问题的最优解与贪心选择组合在一起就能生成原问题的最优解。

  1. 赫夫曼编码
    讨论赫夫曼编码问题，赫夫曼编码的思想就是变长编码。变长编码就是让字符表中出现概率高的字符的编码长度尽可能小，而出现概率高的字符的编码长度相对较长。然后还要遵循前缀码的要求，就是任意一个编码都不是其他编码的前缀码，这样方便解码。

构造赫夫曼编码
Huffman(C)
n = |C|
Q = C
for i = 1 to n
allocate a new node z
z.left = x = Extract-Min(Q)
z.right = y = Extract-Min(Q)
z.freq = x.freq + y.freq
Insert(Q, z)
return Extract-Min(Q) // return
第十七章 摊还分析
17.1 聚合分析

用来确定一个n个操作的序列的总代价的上界T(n).

由n个push，pop，multi-pop组成的操作序列。依赖于push
二进制计数器递增
　　　　A[0]每次都翻转，A[1]每两次翻转一次，A[2]每两次翻转一次...

17.2 核算法

　　较早操作的余额（overcharge）作为预付信用（prepaid credit）储存起来，与数据结构中的特定对象相关联。对应后续操作中摊还代价小于实际代价的情况，信用可以用来支付差额。

17.3 势能法

势能法摊还分析并不将预付代价表示为数据结构中特定对象的信用，而是表示为“势能”，或简称“势”，将势能释放即可用来支付未来操作的代价。我们将势能与整个数据结构而不是特定对象相关联。

工作方式如下：

我们将对一个初始数据结构D0执行n个操作。对每个i=1，2，。。。，n，令ci为第i个操作的实际代价，令Di为在数据结构Di-1上执行第i个操作得到的的结果数据结构。势函数Φ将每个数据结构Di映射到一个实数Φ（Di），此值即为关联到数据结构Di的势。第i个操作的摊还代价c‘i用势函数Φ定义为

c‘i=ci+Φ（Di）-Φ（Di-1）

总摊还代价为
栈操作：可定义栈的势为栈中的对象数量。

二进制计数器：可定义计数器的势为其中1的位数。

17.4 动态表

17.4.1 表扩张

17.4.2 表扩张和收缩

总之，由于每个操作的摊还代价的上界是一个常数，在一个动态表上执行任意n个操作的实际运行时间是O(n)。