动态规划和贪婪算法
动态规划：(背包问题，旅游行程最优化)
是一种解决棘手问题的方法，它将问题分成小问题，并先着手解决这些小问题。
仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。
问题：
1.生物学家根据最长公共序列来确定DNA链的相似性，今儿判断两种动物或疾病有多相似。最长公共序列还被用来寻找多发性硬化症治疗方案。
2.git diff命令，指出两个文件的差异，也是使用动态规划实现的。
3.字符串的相似程度。编辑距离指出了连哥哥字符串的相似程度，也是使用动态规划计算得到的。
小结：
1.需要在给定约束条件下优化某种指标时，动态规划很有用。
2.问题可分解为离散自问题时，可使用动态规划来解决。
3.每种动态规划解决方案都涉及网格。
4.单元格中的值通常就是你也要优化的值。
5.每个单元格都是一个子问题，因此需要考虑如何将问题分解为自问题。
贪婪算法：(旅行商问题，广播台问题)
贪婪算法解决问题的时候，每一步都可以做出一个贪婪的选择，基于这个选择，我们确定能够得到最优解。
NP完全问题：
1.元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
2.涉及”所有组合”的问题通常时NP完全问题。
3.不能将问题分成小问题，必须考虑各种可能的情况。
4.如果问题涉及序列(如旅行商问题中的城市序列)且难以解决，它可能就是NP完全问题。
5.如果问题涉及集合(如广播台集合)且难以解决，它可能就是NP完全问题。
6.如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。
问题：
1.有个邮递员负责给20个家庭送信，需要找出经过这20个家庭的最短路径？请问这是一个NP完全问题吗？
2.有一堆人中超出最大的朋友圈(即其中任何两个人都相识)？是NP完全问题么？
3.你要制作美国地图，需要用不同的颜色标出相邻的州。为此，你需要确定最少需要使用多少种颜色，才能保证任何两个相邻州的颜色都不同。请问这是NP完全问题吗？
小结：
贪婪算法寻找局部最优解，企图已这种方式获得全局最优解。
对于NP完全问题，还没有找到快速解决方案。
面临NP完全问题是，最佳的做法是使用近似算法。
贪婪算法易于实现、运行速度快，是不错的近似算法。
