数据结构与算法-动态规划与贪心算法

[tianma630]

本文基于《javascript数据结构与算法》一书

动态规划

动态规划(Dynamic Programming，DP)是一种将复杂问题分解成更小的子问题来解决的优化技术。用动态规划解决问题时，要遵循三个重要步骤:

1. 定义子问题;
2. 实现要反复执行而解决子问题的部分;
3. 识别并求解出边界条件。

插入排序就是动态规划的思想

贪心算法

贪心算法遵循一种近似解决问题的技术，期盼通过每个阶段的局部最优选择(当前最好的 解)，从而达到全局的最优(全局最优解)。它不像动态规划那样计算更大的格局。