算法笔记：详细总结分治法，动态规划，贪心算法以及各算法典型例题

心已赠人 2022-02-05 09:45 428阅读 0赞

### 文章目录 ###

*  一，三种算法的基本思想
 *   *  分治法
     *  动态规划
     *  贪心算法
 *  二，三种算法的对比
 *   *  分治与动态规划。
     *  贪心与动态规划。
 *  三，三种算法的基本题型（不断更新中。。。）
 *   *  分治法
     *  动态规划
     *  贪心

# 一，三种算法的基本思想 #

## 分治法 ##

分治法的基本思想是将一个规模为ｎ的问题分解为ｋ个规模较小的问题，**这些子问题互相独立且与原问题相同（所以可以递归**,递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。

## 动态规划 ##

动态规划算法和分治法相似的地方是它也是将待求解问题分成若干子问题，然后从这些子问题的解得到原问题的解。但与分治法不同的是，适合动态规划法解的题，经分解得到的子问题往往**不是相互独立的**若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。  
　　  
　　  
能用动态规划解的问题有如下三个性质：  
　  
　  
　**1. 最优子结构性质**  
　　**当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质**简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。在动态规划算法中，利用问题的最优子结构性质，以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。  
　  
　  
　**2. 无后效性**  
　　将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，**每个状态都是过去历史的一个完整总结**这就是无后向性，又称为无后效性。

**3. 重叠子问题**  
　　在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新的子问题，\*\*有些子问题被反复计算过多次。\*\*动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其保存在一个表格中，当再次需要解此问题时，只是简单地用常数时间看一下结果。

## 贪心算法 ##

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，**不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。**  
　　贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。  
　　因此贪心算法具有最优子结构性质和贪心选择性质。  
　　1.最优子结构（同上）  
　　**2.贪心选择性质**  
　　 所谓贪心的选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这也是贪心算法和动态规划算法的主要区别。**在动态规划算法中，每步所做的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能做出选择。而在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择**正是由于这种区别，动态规划算法通常以自底向上的方式解决个子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。  
　　 贪心算法的示例也有很多，比如数据结构中的Prim算法、Dijkstra算法和Huffman算法等。

# 二，三种算法的对比 #

## 分治与动态规划。 ##

分治和动态规划都是将问题分解为子问题，然后合并子问题的解得  
到原问题的解。但是不同的是，分治法分解出的子问题是不重叠的，因此**分治法解决的问题不拥有重叠子问题，而动态规划解决的问题拥有重叠子问题**。例如，归并排序和快速排序都  
是分别处理左序列和右序列，然后将左右序列的结果合并，过程中不出现重叠子问题，因此  
它们使用的都是分治法。另外，分治法解决的问题不一定是最优化问题，而动态规划解决的  
问题一定是最优化问题。

## 贪心与动态规划。 ##

贪心和动态规划都要求原问题必须拥有最优子结构。

二者的区别于，贪心法采用的计算方式类似千上面介绍的”自顶向下”，但是并不等待子问题求解完毕再选择使用哪一个，而是通过一种策略直接选择一个子问题去求解，没被选择的子问题就去求解了，直接抛弃。也就是说，**它总是只在上一步选择的基础上继续选择，因此整个过以一种单链的流水方式进行，显然这种所谓“最优选择”的正确性需要用归纳法证明**例对数塔问题而言，贪心法从最上层开始，每次选择左下和右下两个数字中较大的一个，一到最底层得到最后结果，显然这不一定可以得到最优解。而动态规划不管是采用自底向上是自顶向下的计算方式，都是从边界开始向上得到目标问题的解。也就是说，它总是会考所有子问题，并选择继承能得到最优结果的那个，对暂时没被继承的子问题，由千重叠子题的存在，后期可能会再次考虑它们，因此还有机会成为全局最优的一部分，不需要放弃所以贪心是一种壮士断腕的决策，只要进行了选择，就不后悔；动态规划则要看哪个选择到了最后，暂时的领先说明不了什么。

# 三，三种算法的基本题型（不断更新中。。。） #

## 分治法 ##

[输油管道问题][Link 1]  
[邮局选址][Link 2]

## 动态规划 ##

[数塔问题][Link 3]  
[最大连续字段和][Link 4]  
[最长非递减子序列][Link 5]  
[最长公共子序列][Link 6]  
[最长回文串][Link 7]

## 贪心 ##

[Link 1]: https://blog.csdn.net/i6223671/article/details/88752406
[Link 2]: https://blog.csdn.net/i6223671/article/details/88807376
[Link 3]: https://blog.csdn.net/i6223671/article/details/89788714
[Link 4]: https://blog.csdn.net/i6223671/article/details/89789503
[Link 5]: https://blog.csdn.net/i6223671/article/details/89791605
[Link 6]: https://blog.csdn.net/i6223671/article/details/89812862
[Link 7]: https://blog.csdn.net/i6223671/article/details/89815073