算法和数据结构是每个程序员都必须修炼的内功，在面试的时候或多或少都会被问到一些算法相关的问题。

算法的应用不单只体现在编程中。狭义的来讲，算法可看作是数据传递和处理的顺序、方法和组成方式，就像是各种排序算法等。广义的来讲，算法更像是一种事物运行的逻辑和规则。

算法其实是一种思维模式，本文就简单介绍一下八种常用算法思想，分别是枚举、递推、递归、分治、动态规划、贪心、回溯和模拟。

最简单的枚举算法，也被称为穷举，顾名思义就是穷尽列举。枚举思想的应用最为广泛，也最是通俗易懂。枚举思想是将问题的可能解依次全部列举，然后一一带入问题内检验，从而找到正确解。

枚举思想其实有一种兵分多路的意思，就是从多个样本中依次试错找到正确结果，当然弊端也是显而易见——试错成本。还存在一些容易叫人忽视的问题，比方说待解决问题的「可能解 / 候选解」的筛选条件，「可能解」之间相互的影响，穷举「可能解」的代价，「可能解」的穷举方式等等。

枚举思想用以下图形表示：

百钱买百鸡问题 公鸡一个五块钱，母鸡一个三块钱，小鸡三个一块钱，现在要用一百块钱买一百只鸡，问公鸡、母鸡、小鸡各多少只？

递推思想与枚举思想类似，都很符合人类的思维方式，人脑在面临未知问题时，第一反应是根基定性思维，从已知推导未知，从而得到解决问题的方法。

递推，顾名思义就是递次推导，递推思想的核心就是从已知的条件出发，逐步推算出问题的解。条件与结果中间存在着某种因果关系，这种条件关系可能人脑思维很容易想通，但是对于计算机而言，复杂的推导其实很难实现。计算机擅长的是执行高密度重复性高的工作，因此计算机在运用递推思想时，大多是重复性推理。举个例子，从「今天是 1 号」推出「明天是 2 号」，以此推导出以后的日期。这种推理的结构十分类似，往往可以通过继而往复的推理就可以得到最终的解。

递推思想用图解来表示可以参见下图。每一次推导的结果可以作为下一次推导的开始，这似乎跟迭代、递归的思想有点类似，不过递推的范畴要更广一些。

兔子问题 一对大兔子每月能生一对小兔子，且每对新生的小兔子经过一个月可以长成一对大兔子，具备繁殖能力，如果不发生死亡，且每次均生下一雌一雄，问一年后共有多少对兔子？

说完递推，就不得不说说它的兄弟思想——递归算法。二者同样都带有一个「递」字，可以看出二者还是具有一定的相似性的。「递」的理解可以是逐次、逐步。在递推中，是逐次对问题进行推导直到获得最终解。而在递归中，则是逐次回归迭代，直到跳出回归。

递归算法实际上是把问题转化成规模更小的同类子问题，先解决子问题，再通过相同的求解过程逐步解决更高层次的问题，最终获得最终的解。所以相较于递推而言，递归算法的范畴更小，要求子问题跟父问题的结构相同。

用一句话来形容递归算法的实现，就是在函数或者子过程的内部，直接或间接的调用自己算法。所以在实现的过程中，最重要的是确定递归过程终止的条件，也就是迭代过程跳出的条件判断。否则，程序会在自我调用中无限循环，最终导致内存溢出而崩溃。

递归算法的图解可如下图。很明显，递归思想其实就是一个套娃过程。一般官方都是严禁套娃行为的。所以在使用时一定要明确「套娃」举动的停止条件，及时止损。

汉诺塔问题 源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

分治，分而治之。

分治算法的核心步骤就是两步，一是分，二是治。但这还引申出了一系列的问题，为什么分，怎么分，怎么治，治后如何。

分治算法类似于向下管理的思想，将最终任务化整为零，从最高级层层划分，将子任务划分给不同的子模块，进而可以进行大问题的拆分，对系统问题的粒度进行细化，寻求最底层的最基本的解。这样的思路在很多领域都有运用，比如几何数学中的正交坐标、单位坐标、基的概念等，都是通过将复杂问题简化为基本的子问题，然后通过先解决子模块再逐步解决主模块。

在实际的运用中，分治算法主要包括两个维度的处理，一是自顶向下，将主要问题逐层级划分为子问题；二是自底向上，将子问题的解逐层递增融入主问题的求解中。

那为什么要分？这个很好解释，由于主要问题的规模过大，无法直接求解，所以需要对主要问题进行粒度划分。

那怎么分？遵循计算机最擅长的重复运算，划分出来的子问题需要相互独立并且与原问题结构特征相同，这样能够保证解决子问题后，主问题也就能够顺势而解。

怎么治？这就涉及到最基本子问题的求解，我们约定最小的子问题是能够轻易得到解决的，这样的子问题划分才具有意义，所以在治的环节就是需要对最基本子问题的简易求解。

治后如何？子问题的求解是为了主问题而服务的。当最基本的子问题得到解后，需要层层向上递增，逐步获得更高层次问题的解，直到获得原问题的最终解。

分治思想的图解可见下图。通过层层粒度上的划分，将原问题划分为最小的子问题，然后再向上依次得到更高粒度的解。从上而下，再从下而上。先分解，再求解，再合并。

归并排序

讲完分治，我们知道分治思想最重要的一点是分解出的子问题是相互独立且结构特征相同的。这一点并不是所有问题都能满足，许多问题划分的子问题往往都是相互重叠且互相影响的，那么就很难使用分治算法进行有效而又干净的子问题划分。所以有了动态规划。

动态规划同样需要将问题划分为多个子问题，但是子问题之间往往不是互相独立的。当前子问题的解可看作是前多个阶段问题的完整总结。因此这就需要在子问题求解的过程中进行多阶段的决策，同时当前阶段之前的决策都能够构成一种最优的子结构。这就是所谓的最优化原理。

最优化原理，一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。同时，这样的最优策略是针对已作出决策的总结，对后来的决策没有直接影响，只能借用目前最优策略的状态数据。这也被称之为无后效性。

动态规划是在目前看来非常不接近人类思维方式一种算法，主要原因是在于人脑在演算的过程中很难对每一次决策的结果进行记忆。动态规划在实际的操作中，往往需要额外的空间对每个阶段的状态数据进行保存，以便下次决策的使用。

动态规划的求解思路如下图解。动态规划的开始需要将问题按照一定顺序划分为各个阶段，然后确定每个阶段的状态，如图中节点的 F0 等。然后重点是根据决策的方法来确定状态转移方程。也就是需要根据当前阶段的状态确定下一阶段的状态。在这个过程中，下一状态的确定往往需要参考之前的状态。因此需要在每一次状态转移的过程中将当前的状态变量进行记录，方便之后的查找。 动态规划主要就是用来解决多阶段决策的问题，但是实际问题中往往很难有统一的处理方法，必须结合问题的特点来进行算法的设计，这也是这种算法很难真正掌握的原因。

背包问题 有 n 件物品和容量为 m 的背包，给出物品的重量以及价值。求解让装入背包的物品重量不超过背包容量且价值最大 。

贪心算法——最现实的算法思想。

人活在世上，不可能每一个选择都那么恰到好处。那么多的问题，不可能所有问题都能找到最优解。很多问题根本没有准确解，甚至于无解。所以在某些场景下，傻傻地去追求问题的最精确解是没有意义的。

有人说，那还有最优解呢。难道最优解都不要了吗？

没错，许多问题虽然找不到最精确的解，但是的确会存在一个或者一些最优解。但是一定要去追求这些最优解吗？我看不一定。

算法的存在不是单纯地为了对问题求解，更多的是提供一种「策略」。何谓「策略」，解决问题的一种方式，一个角度，一条路。所以，贪心思想是有价值的。

说回贪心算法。从贪心二字就可得知，这个算法的目的就是为了「贪图更多」。但是这种贪心是「目光短浅」的，这就导致贪心算法无法从长远出发，只看重眼前的利益。

具体点说，贪心算法在执行的过程中，每一次都会选择最大的收益，但是总收益却不一定最大。所以这样傻白甜的思路带来的好处就是选择简单，不需要纠结，不需要考虑未来。

贪心算法的实现过程就是从问题的一个初始解出发，每一次都作出「当前最优」的选择，直至遇到局部极值点。贪心所带来的局限性很明显，就是无法保证最后的解是最优的，很容易陷入局部最优的情况。

但是它每一次做选择的速度很快，同时判断条件简单，能够比较快速地给出一种差不多的解决方案。

旅行推销员问题 给定一系列城市和每对城市之间的距离，求访问每一座城市一次并回到起始城市的最短回路。

回溯算法也可称作试探算法，简单来说，回溯的过程就是在做出下一步选择之前，先对每一种可能进行试探；只有当可能性存在时才会向前迈进，倘若所有选择都不可能，那么则向后退回原来的位置，重新选择。

我们如果把枚举看作是兵分多路，那回溯则是”摸着石头过河”的“侦察兵“思想，回溯算法很像是一种进行中的枚举算法，在行进的过程中对所有可能性进行枚举并判断。常用的应用场景就在对树结构、图结构以及棋盘落子的遍历上。

回溯思想在许多大规模的问题的求解上都能得到有效的运用。回溯能够将复杂问题进行分步调整，从而在中间的过程中可对所有可能运用枚举思想进行遍历。这样往往能够清晰地看到问题解决的层次，从而可以帮助更好地理解问题的最终解结构。

八皇后问题 在 8×8 格的国际象棋上摆放 8 个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

许多真实场景下，由于问题规模过大、变量过多等因素，很难将具体的问题抽象出来，也就无法针对抽象问题的特征来进行算法的设计。这个时候，模拟思想或许是最佳的解题策略。

模拟的过程就是对真实场景尽可能的模拟，然后通过计算机强大的计算能力对结果进行预测。这相较于上述的算法是一种更为宏大的思想。在进行现实场景的模拟中，可能系统部件的实现都需要上述几个算法思想的参与。

模拟说起来是一种很玄幻的思想，没有具体的实现思路，也没有具体的优化策略。只能说，具体问题具体分析。

那应该怎么样来图解呢。我的理解是自定义的，任意的输入，不规则的系统响应，但是只为了获得一个可靠的理想的输出。