前言
虽然我是一个连jquery都用的不熟的人，但作为前端开发学习人员，总是要追求一下新的技术，所以最近就看了一下很火的React这个东西，但本篇文章并非讲的是React的内容，而是在学习React的过程中，其使用了DOM Diff算法，然后我又查到了Diff算法，然后Diff算法又属于动态规划的算法思想，然后我就打开了买来许久，不曾翻阅过的《算法的分析这本书》，好好了解一下算法设计中的常用思想，记录一下学习的内容吧。
贪婪法
贪婪法简介
贪婪法是寻找最优解问题的常用方法。这种方式一般将求解过程分为若干个步骤，每个步骤都使用贪心原则，选取对局部最有利的选择。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。它是一种启发式辅助算法。
与其他算法比较：
- 相同点：对问题进行分解，定义最优解的子结构
- 不同点在每一步选择完后就确定了局部最优解，不在进行回溯处理
特点：
- 优点：简单高效，不需穷举，可得到近似最优解
- 缺点：选择策略”短视“，错过真正的最优解
举例：
- 题目：有25分、10分、5分、1分四种硬币，要给客户找41分硬币，且硬币个数最少。
- 分析：子问题的最优解结构就是在之前的步骤中已经选的硬币上加上当前选择的硬币。即在币值不超过41的前提下选择币值最大的一枚硬币。则根据贪婪法，第一次选25分，之后依次选择10分，5分，1分。需要4枚，确实是最优解。
- 但是若换成25分、20分、5分、1分四种硬币，则这时候最优解应该是2枚20分1枚1分。但是根据贪婪法得到的结果则为1枚25分3枚5分1枚1分共5枚硬币。
分治法
分治法简介
将无法着手解决的问题分解成一系列规模较小的相同问题，反复使用分治方法，知道能够被直接求解为止
应用：
- 最大最小问题，如在一堆形状相同的物品中找到最重或最轻的一个
- 快速排序、大整数算法等
特点：
- 最难和最灵活的部分就是对问题的分解和结果的合并
- 经常使用递归的方法
动态规划法
动态规划法简介
将多阶段决策过程转化为一系列的单阶段决策问题，利用各个阶段之间的递推关系，逐个确定每个阶段的最优化决策，最终堆叠出多阶段决策的最优化决策结果
应用：
- 最短路线、库存管理、资源分配等
- 快速排序、大整数算法等
特点：
- 最难和最灵活的部分就是对问题的分解和结果的合并
- 经常使用递归的方法
