算法导论笔记5：贪心算法

P216 第15章动态规划 最优子结构 具有它可能意味着适合应用贪心策略

动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法。

剪切-粘贴技术证明 每个子问题的解就是它本身的最优解（利用反证法）

保持子问题空间尽可能简单

P217 在第16章介绍贪心算法，它与动态规划有很多相似之处，最大的不同在于贪心算法不是首先寻找子问题的最优解，然后在其中进行选择，而是首先做出一次贪心选择得到当时（局部）最优解，然后求解选出的子问题——（感觉这点也可以用于生活琐事，是不是最优选择先做了再说，当然也有一定的基础证明这么做结果不会太差）

P218 两个最长简单路径子问题是相关的，两个最短路径子问题是无关的（什么是无关：无关是同一个原问题的一个子问题的解不影响另一个子问题的解）

重叠子问题 适合动态规划方法求解的最优化问题应该具备的第二个性质是子问题空间必须是足够小，即问题的递归算法会反复求解的相通的子问题（这就是重叠子问题），而不是一直生成新的子问题。

P219 15.1节 钢条切割问题的递归算法是如何通过指数次的递归调用来求解小的子问题。动态规划算法讲运行时间从递归算法的指数阶降为平方阶。

P222 最长公共子序列（LCS） 举例：用于比较两个DNA串的相似度

定理15.1 LCS的最优子结构

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

步骤2：一个递归解；

步骤3：计算LCS长度；

步骤4：构造LCS

P226 LCS_LENGTH 的空间需求是可以逐渐减小的

应用案例：设计程序实现语言之间翻译，用最优二叉搜索树（optimal binary search tree，求解它与矩阵乘法相似），提高搜索效率，让频繁出现的单词靠近跟，冷门的词汇远离根。

P237 第16章 贪心算法greedy algorithm，这章有拟阵（matroid）的概念，从贪心算法中衍生出来的

P238 用举办活动的选择问题来解释贪心算法

P242 贪心选择的性质，贪心算法通常是自顶向下的

贪心算法和动态规划算法，二者间有细微差别。

研究一个经典最优化问题的两个变形：0-1背包问题，分数背包问题

0-1背包问题：小偷偷商品，对于任何一个商品要么完整拿走，要么留下，不能只拿一部分或一个商品反复拿

分数背包问题：具备贪心选择性质

引申检索：贪心算法有什么应用

1 关于视频传输领域，查找到一个专利：一种基于贪心算法的全景视频传输方法

针对的是全景视频：对接收到的全景视频进行片段划分，得到若干视频片段；对每个所述视频片段进行块划分，得到与每个所述视频片段对应的基本块集；根据预设的贪心合并分块算法对每个所述基本块集进行处理，得到对应的目标分块集；根据所述目标分块集对所述全景视频进行视频传输。

2 关于视频拼接领域，查找到一个算法题：

获得一系列视频片段，这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。视频片段 clips[i] 都用区间进行表示：开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, T]）。返回所需片段的最小数目。