算法

时间复杂度 & 空间复杂度

贪婪法（Greedy Algorithm），又称贪心算法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好的或最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好或最优的解。贪婪法的每次决策都以当前情况为基础并根据某个最优原则进行选择，不从整体上考虑其他各种可能的情况。一般来说，这种贪心原则在各种算法模式中都会体现，这里单独作为一种方法来说明，是因为贪婪法对于特定的问题是非常有效的方法。
贪婪法和动态规划法以及分治法一样，都需要对问题进行分解，定义最优解的子结构，但是与其他方法最大的不同在于，贪婪法每一步选择完局部最优解之后就确定了，不再进行回溯处理，也就是说，每一个步骤的局部最优解确定以后，就不再修改，直到算法结束。

分治法（Divide and Conquer）也是一种解决问题的常用模式，分治法的设计思想是将无法着手解决的大问题分解成一系列规模较小的相同问题，然后逐个解决小问题，即所谓分而治之。分治法产生的子问题与原始问题相同，只是规模减小，反复使用分治方法，可以使得子问题的规模不断减小，直到能够被直接求解为止。
应用分治法，一般出于两个目的，其一是通过分解问题，使得无法着手解决的大问题变成容易解决的小问题，其二是通过减小问题的规模，降低解决问题的复杂度（或计算量）。

数学意义上的迭代法是一种不断用变量的旧值递推新值的过程，其对应的迭代算法也是用计算机解决问题的一种基本方法。
迭代法一般用于求解数学问题，比如求解一元高次方程、线性和非线性方程组和曲线拟合等问题。迭代的基本点就是迭代公式，一般也理解为递推公式，这常常让人对迭代法和递推法产生混淆，认为这两个概念是等同的。事实上，这两个概念还是有点差异的，迭代法作为很多数学问题的求解算法，是解决数学问题的一种常用的算法模式，可以独立构成解决问题的算法。递推法作为一种设计算法的常用思想，没有固定的算法实现模式，通常是与其他算法模式配合形成算法实现。

动态规划（Dynamic Programming）是解决多阶段决策问题常用的最优化理论，动态规划和分治法一样，也是通过定义子问题，先求解子问题，然后在由子问题的解组合出原问题的解。但是它们之间的不同点是分治法的子问题之间是相互独立的，而动态规划的子问题之间存在堆叠关系（递推关系式确定的递推关系）。
动态规划方法的原理就是把多阶段决策过程转化为一系列的单阶段决策问题，利用各个阶段之间的递推关系，逐个确定每个阶段的最优化决策，最终堆叠出多阶段决策的最优化决策结果。动态规划问题有很多模型，常见的有线性模型、（字符或数字）串模型、区间模型、状态压缩模型，等等，本节课后面介绍的最长公共子序列问题，就是一个典型的串模型。

动态规划适合求解多阶段（状态转换）决策问题的最优解，也可用于含有线性或非线性递推关系的最优解问题，但是这些问题都必须满足最优化原理和子问题的“无后向性”。
- 最优化原理：最优化原理其实就是问题的最优子结构的性质，如果一个问题的最优子结构是不论过去状态和决策如何，对前面的决策所形成的状态而言，其后的决策必须构成最优策略。也就是说，不管之前的决策是否是最优决策，都必须保证从现在开始的决策是在之前决策基础上的最优决策，则这样的最优子结构就符合最优化原理。
- 无后向性（无后效性）：所谓“无后向性”，就是当各个阶段的子问题确定以后，对于某个特定阶段的子问题来说，它之前各个阶段的子问题的决策只影响该阶段的决策，对该阶段之后的决策不产生影响。