ACM+DP+算法++大集合

1、第 27 讲 贪心与动态规划     贪心和动态规划在算法设计求解中均有着广泛的应用，因为它们都属于最优化问题的求解，因此这里将它们放在同一章节加以介绍。    虽然都是求解最优化问题，但是贪心和动态规划还是有很大的区别的。前者是从问题的源出发每一步都采取最优的选择，最终找到问题的解；而后者则从考虑问题的子问题入手，通过比较划分后的独立子问题的解，来确定当前问题的最优解。相对而言，贪心法的形式非常多样，不容易对它做具体的分类，许多算法之中都蕴含了贪心的思想，而动态规划则可以大致分出一些应用较多的独立模型。因此在这一

2、章节，我们会把笔墨侧重于后者。 第一部分 贪心(Greedy)    在求解最优化问题时，有这样一种自然的想法，希望每一步都则采取最优的策略，最终得到全局的最优解，这就是贪心思想。它的最大特点就是运行速度快，效率高，因此备受程序设计员的喜爱。当然，由此也带来了贪心法的最大问题，如何证明其正确性？因为在很多时候，局部最优解的选择往往最终得不到全局最优解。于是，我们在运用贪心思想解决问题时，就需要格外的小心。    事实上，许多成熟的算法中都蕴含了贪心思想，比如求解最小生成树的Bellman-Ford算法，单源最短路径的Dijk

3、stra算法，求解二分图匹配的匈牙利算法等等。    很多时候，贪心法虽然得不到最优解，但是仍具有重要的最用。比如，利用贪心法得到的近似解可以为搜索法提供较强的剪枝策略。就用一个例子来看看贪心法的应用吧：例 1, POJ 2287 田忌赛马田忌赛马的故事想必已经被大家所熟知了，孙膑“以君之下驷彼上驷，取君上驷与彼中驷，取君中驷与彼下驷”的策略使得田忌最终“一不胜而再胜”。如今，田忌与齐王决定再战一场，这一回双方决定用 n (n 1000)匹马较量一番。每一回合，先到的马将为主人赢得200美元，如果打平双方均无需指出。假设双方马匹的速度已给出，而田忌仍然能够提前知道

4、齐王马匹的出场顺序，那么他最多能赢多少钱呢？分析乍看下去，似乎没有很好的贪心思路，倒是可以利用二分图匹配的方法解题，可是时间复杂度相对较高，改进得的匈牙利算法也匹配需要O（n3）的时间，即使Hopcraft算法，也需要O（）的时间复杂度。那么，真的不能运用贪心法吗？当年田忌获胜的方法或许能够给我们一些启迪。用下等马匹配齐王的上等马，虽然输掉了局部，却赢下了全局。也就是说，在最终的最优选择中，将有一些场次会输掉比赛。那么，既然是这样，我们何不学习田忌，用那些“下等马”输掉这些比赛，而让获胜者，均为齐王的“上等马”呢？这样的改进不会比原先的最优选择更差。设An为田忌的马，且按速度排序A1 >

5、 A2 > > An ,Bn为齐王的马，同样按速度排序B1 > B2 > > Bn ,假设Ap会输给它的对手，而Aq（p < q）的选择使它至少不输掉该场比赛，那么将二者的对手对调，所得结果显然不会比之前更差；同样，若Bp不输给它的对手，而Bq（p > q）则输给了它的对手，那么将再二者的对手对调，结果仍不会次于调换前。于是，调换后见下图：A1A2.An-1AnB1B2.Bn-1BnA1A2.An-1AnB1 红线代表输的场次B2 为了看得更清晰， . 红线间若有交叉可通过. 调整将其变为一组平行Bn-1 线，不会影响结果Bn  图1-1 最

6、优策略                      图1-2 改进后既然改进前是最优策略，那么改进后它必然也是最优策略。而改进后的图与田忌赛马有着异曲同工之处，那么顺着它的思路，我们似乎又有了另一个改进策略。在图1-2中除去所有输掉比赛的A以及它们的对手，剩下的图中所有的“交叉”都可以去掉。即假设Ap的对手为Br,Aq的对手为Bs，而p<q,r>q，那么我们可以对调双方的对手，

7、显然结果不会变差。于是，改进后的图变成了如下：                        A1A2.An-1AnB1B2.Bn-1Bn                    &

8、#160;          图 1-3 最终策略显然，这个最终策略仍然是最优策略。于是，我们只需要枚举输掉的比赛场次，逐个判断是否满足上述策略的要求，就能够找到最优解。 第二部分 动态规划（Dynamic Programming）动态规划是解决最优化问题的重要手段，它的优美精巧的结构特点深得程序设计员的喜爱，一段短小精悍的代码就能解决长长的回溯法所不能解决的问题，这是动态规划最吸引人的特点。动态规划是通过合并子问题的解来解决最优化问题的。许多时候，一个问题的若干子问题往往不是独立存在的，而和其

9、它问题的子问题相同，于是对这些公共子问题的采取先计算求解并存值得方式，以便为将来反复调用时直接提供值，就成了动态规划的主体思想。可以看到，实现动态规划需要满足如下条件：1) 最优子结构性质，也就是说问题最优解与子问题的最优解有关。2) 无后效性，就是说问题的解只与已求得的子问题的解有关，与尚未求得的问题的解无关联。可以看到，这就需要问题的求解具有明显的层次性。因此，在求解此类问题时，我们需要将其划分成若干个层次，并找到层与层之间的关联，即“状态转移方程”。随后自底向上逐层求解。动态规划的一般形如：算法2-1：for (用i枚举所有状态)    for （用j枚举所

10、有上层状态）    利用状态j来更新状态i的最优值。下面来看一些动态规划的经典模型。1. 背包问题背包问题是动态规划问题中最为经典的模型之一，我们来看看它的简要描述：例 2 有一个能容积为V的背包，现在有N件物品，它们的容积和价值分别用An和Bn表示，现在问如何选择物品放入背包，才能使背包在没有超载的情况下物品价值总和最大。分析可以看到，背包中物品的顺序是没有要求的，因此我们可以逐个考虑每个物品。如果用一个一维数组Cn记录考虑到当前物品i为止时，容积为j(0 j V)的情况下，可以达到的最大价值为Cj，那么状态转移方程如下： 这里要注意两点，第一是公式中

11、重量j A(i)必须是一个在之前已经达到过了的可行解，否则C(j A(i)是无效的，第二是j的循环顺序必须是从大到小，可以有效地防止在同一轮i的情况下，刚刚修改的C(j-A(i)值对当前的C(j)产生影响。尽管背包问题还有不少变化的情况，但只要分析清楚层次，列出正确的转移方程，那么就能比较容易地解决它。2. 最长公共子串（LCS）问题最长公共子串问题同样是动态规划问题中的经典模型，再来看看它的简要描述：例 3 假设有两个字符串A,B，求它们最长的公共子串C。其中，“子串”的定义为，设P = p1p2pm，那么串Q称为串P的长为t“子串”，如果满足Q = pq1pq2pqt，其中1 t n, q

12、1 < q2 < < qt。如果C既为A的子串，又为B的子串，那么就称C为A和B的公共子串。分析     先来看看一个例子，假设A = acdefgad, B = bcaedafg                             a c d e f g

13、a db c a e d a f g  它们的最长公共子串C = aefg 或 cefg。可以看到，如果将A的最后一个字母去掉，并没有改变它们的最长公共子串，而如果将B的最后一个字母去掉，那么最长公共子串长就少了1。原因在于，B的最后一个字母g与A中的第6个字母g可匹配。于是我们考虑一般的情形：两个字符串求LCS，如果它们的串尾均没有作出“贡献”，那么它们的LCS等价于删去串尾后两个字符串的LCS；如果串尾有所“贡献”，那么要看着这个串尾是否相等。若相等，显然可将二者连线；反之，就要看哪个“贡献”对LCS更有帮助了。如果以L(i, j)表示A串的前i个字符和B串的前j个字符

14、的最长公共子串长，那么刚才的文字描述用公式表示就是：                     可以看到L(i,j)的值只与L(i-1，j),L（i，j-1）和L(i-1，j-1)有关，这就具有明显的层次关系。按照上述转移方程就可求解最长公共子串的长。至于求出具体的串，那么只要在求解过程中记录下每一次的选择，最后根据最长串的串尾进行一遍倒推即可得到最长子串。3. 树型动态规划一个无环连通图便称为一棵

15、树，由于树具有明显的层次关系，因此很多关于它的最优化问题都可以用动态规划的方法解决，可以把这一类方法归纳为树型动态规划。一些问题需要自己建立一颗树，再利用动态规划的方法解决，一些问题则本身就是以树为背景的。来看看下面这个例子：例 4, POJ1655给定一棵有N(1 N 20000)个结点的树T，定义结点的“平衡度”如下：删去该结点后，在剩下的结点构成的森林中，最大树的结点数。于是，我们的问题是，在树T中，找到平衡度最小的结点。分析看完题目，最直接的想法自然是枚举每个点，然后求它的平衡度，也就是遍历这棵森林。但是，这种做法的时间复杂度至少是O(N2)。对于如此大的N，这显然太慢了，有没有更好的

16、方法呢？让我们再仔细分析一下，遍历一次树T，我们能得到多少信息。对于一个结点A，必然是由某个结点B遍历过来，然后遍历它的所有后继C、D。，如果我们能得到A的所有后继结点分别又遍历到了多少结点，那么我们就可以知道B结点之前已经遍历了多少结点，于是，所有与A有连接的结点块的信息便都得到了。那么也就求得了A的平衡度。如果用Num(A)表示结点A和它的所有后继的个数，那么上述分析可用以下公式表示：        利用上述公式，用Dfs对树进行一遍遍历就能找到平衡度最小结点的平衡度，稍加分析便可知，答案最多只有两个点。此外，此题的另一

17、个要注意的问题便是如何保存这棵树。如果直接用邻接数组表示，那么内存消耗太大。一般有三种方法，一是用邻接链表保存，把所有与某个结点相邻的结点用一个链表串起来；二是将与结点1,2,3,N相邻的结点顺序的记录在一个数组中，然后为每个结点记录两个值，即与它相邻的结点在线形数组中的区间的端点；三是用vector容器保存。前两个方法都是利用了树是稀疏图，边数很少的性质来考虑的。4. 状态压缩动态规划有一些问题，我们无法用单独的状态运用动态规划，但是可是将一组状态合并为一个状态，并且合并以后可以看到明显的层次关系和最优子结构的性质，这样的手段就是状态压缩动态规划，一般简称状态DP。许多时候由于单独的状态可以

18、用0和1来表示，因此组合后的状态可以用一个普通的数的二进制形式来表示/由于计算机对二进制的表示和处理都非常方便，因此这样的手段为编写代码提供了很大的方便。例 5，POJ 2411给定一个w×h(1w,h11)的矩形，如果用1×2的小矩形去拼装，那么共有多少种不同的拼法？分析刚拿到这题时，可能大多数人的第一感觉是搜索题。可是仔细想想，最大的矩形面积超过了100，用面积为2的方块去拼，显然方法数将是巨大的，搜索看来很难出解。那么有没有其它方法呢？用普通的动态规划考虑似乎也没有什么眉目，一个矩形与它的子矩形之间似乎很难找到什么有价值的关联。换个角度来想，当我们与小矩形去填充时，经常用的手段就是逐层填满，由于小矩