《挑战程序设计竞赛》读书笔记（二）贪心算法 动态规划
本文阅读了《挑战程序设计竞赛》一书的第二章节，做了读书笔记，主要涉及贪心算法和动态规划，包括区间调度问题，01背包的动态规划解法，最长公共子串LCS问题。
过了第一章的热身题之后，随后的题目难多了。本文只是对书中的部分题目，做了笔记。更多题目和详解，读者请参考原书和《算法导论》，《计算机算法设计与分析》（王晓东）等书。
2.2节贪心法
贪心法是不断地取当前最优策略的算法设计方法。
找零钱问题：
对于1,5,10,50,100,500面值的硬币各有Ci个，要支付A元，至少需要几个硬币。
直观上，我们知道，为了使硬币数目最少，则尽量优先使用最大币值的硬币。
区间问题：
有n项工作，每项工作分别在si开始，在ti结束。对于每项工作，你都可以决定是否参加（一旦参加就不必须从头到尾完成该工作）。要求你选择尽量多的工作。注意，同一时间只能做一项工作，也就是选择工作时间区间不能重合。
为了使我们能够选择尽量多的工作，我们希望在选择时，优先选择结束时间早的工作。按照这个贪心策略，可以求得最优解。有其他贪心策略可选，但不一定能够取到最优解。也就是说，贪心算法并不总是能够求出最优解。
通常，我们在给出一个贪心策略后，要证明这个策略能够取到最优解，即该问题该具有贪心选择性质。贪心满足性质是指所求问题的整体最优解可以通过一系列局部最优的选择达到。
对于具体的问题，要确定是否具有贪心选择性质，应该进行证明。通常的证明方法是：(1)先考察问题的一个最优解，然后修改这个最优解使之可以从贪心选择开始；(2)在确定了初始的贪心选择后，原问题变为规模更小的类似子问题，然后通常可以用数学归纳法证明，通过每一步的最优策略选择，最终可以得到问题的整体最优值。第二步的关键在于利用该问题的最优子结构性质（最优子结构性质：如果解S是问题P的最优解，且S包含初始贪心选择a，则S’=S-{a}是子问题P’的最优解）。
2.3动态规划
动态规划是常用的算法设计思想。
动态规划将问题化为子问题，这些子问题通常不是互相独立的。
01背包问题
书中介绍了动态规划求解01背包问题。由于背包问题有多种变体，本文将书中的该问题抄录如下：
有n个重量和价值分别为wi和vi的物品，从这些物品中挑选出总重量不超过W的物体，求所有挑选方案中价值总和的最大值。
动态规划求解问题的4个步骤如下：
1. 找出最优解的性质，并刻画其结构特征。
2. 递归定义最优值。
3. 以自底向上的方式计算最优值。
4. 根据计算最优值时得到的信息，构造最优解。
在上述01背包问题中，我们定义为从第i个物品开始挑选出总重小于j的问题的最优值。
则 i=n时，dp[n][j]=0
i!=n时，
这个公式是说，如果剩余的重量j小于第i个物体的重量，则第i个物体根部就不能放进去，所以。否则，第i个物体可以放进去。当然，即使可以放进去，我们也要查看到底应不应该放进去。所以考察两种情况，一种是将第i个物品放进去，另一种是不放进去。我们取这两个子问题的最优的那个。
在定义了最优值之后，我们要自底向上计算最优值。我们把递归式的计算过程图示化如下：
最长公共子序列（Longest Common Subsequence LCS）
公共子序列不必连续，也就是说，a1b2c3d4和e1f2g3h4的最长公共子序列是1234。
LCS的最优解定义为：
s1 s2 … si和t1 t2 … tj对应的LCS的长度。
则s1 s2 …sisi+1和t1 t2 …tjtj+1对应的LCS可能的情况是：
1. 如果si+1=tj+1，则在s1 s2 …si和t1 t2 …tj的LCS上加上si+1
2. s1 s2 …sisi+1和t1 t2 …tj的LCS
3. s1 s2 …si和t1 t2 …tjtj+1的LCS
所以有如下递归式：
然后自底向上填表就可以了。如果不清楚填表方向，可以像上一道题一样画出表格，标出方向。