算法和数据结构的区别，你知道几个？（上）

算法和数据结构一直是程序员的基本技能。可以说，没有数据结构的基础构建和算法的加持，就不会有近80年的信息革命时代。数据结构可以看作是算法实现的容器。通过一系列具有特殊结构的数据集，可以更高效、更可靠地执行算法。

算法的应用不仅限于编程。狭义的算法可以看作是数据传输和处理的顺序、方法和组成，就像各种排序算法一样。从广义上讲，算法更像是事物运行的逻辑和规则。太阳东升西落，海潮涌动，月亮阴晴不定，这一切看似是一种算法，但执行者不是电脑，而是自然的东西。

离这很远。因此，对于算法的理解，重要的是理解它的思想，感受它的内在。有的同学可能会说，“算法不只是 Leetcode，不就是刷题”。

片面。问题总是无止境的，但算法中只有几个想法。所以，写了这么多题的各位，对这些常见的算法思想是不了解的，还是要好好反省一下。

1个枚举

首先，最简单的想法，枚举算法。枚举又叫穷举，顾名思义就是穷举。枚举思想的应用场景非常广泛，非常容易理解。简单来说，枚举就是依次枚举问题的可能解，然后逐个输入问题进行测试，从而从一系列可能的解中得到能解决问题的确切解。

虽然枚举看起来很简单，但实际上有一些注意事项很容易被忽略。例如，待解决问题的“可能解决方案/候选解决方案”的筛选条件、“可能解决方案”之间的相互影响、穷举“可能解决方案”的成本、“可能解决方案”的穷举方式等。

很多情况下，其实没有必要追求高大复杂的算法结构。相反，途径很简单。枚举的方式可以很好的避免系统复杂带来的冗余，同时在一定程度上可以减少空间。.

枚举思路的流程可以用下图来表示。“可能的解决方案”由实施预先确定，然后在系统中一一验证，并根据验证结果对“可能的解决方案”进行分析论证。这是一种明显的以结果为导向的思想，简单粗暴地试图从最终的结果中反向分析“可能的解决方案”的可行性。

不过，列举想法的弊端当然也很明显。在实际运行的程序中，很少有问题可以通过枚举的方式直接解决。当“可能解决方案”的过滤条件不明确，无法准确确定“可能解决方案”的数量和范围时，枚举就失去了意义。

但是，当“可能的解决方案”的规模比较小，顺序验证的过程很容易实现时，枚举思想是一种方便快捷的方式。但在具体使用中，“可能的解决方案”的验证也可以针对应用场景进行优化。

这种优化可以从两个方向开始。一是简化问题，尽可能简化要处理的问题的模型结构。这种简化可以体现在问题的变量个数上，减少变量的数据，可以从根本上减少“可能解”的组合。

二是严格判断筛选“可能方案”的范围和条件，尽可能排除大部分无效的“可能方案”。

话虽如此，总的来说，大多数无法枚举的场景是由于在有限的空间或有限的时间内无法验证的大量“可能的解决方案”。但实际上，列举思想是最接近人的思维方式，更多时候是用来帮助我们“理解问题”而不是“解决问题”。

案件

一百块钱买一百只鸡的问题。问题描述如下：一只鸡值五只鸡；一个母亲值三个；三只小鸡值一只；一百只鸡值一百块钱，妈妈、妈妈和小鸡多少钱？

翻译过来就是公鸡五元，母鸡三元，小鸡三元。现在我想花一百块钱买一百只鸡。多少只公鸡、母鸡和鸡？

2 递归

与枚举思想一样，递归思想是一种接近人类思维方式的思想，在现实生活中的应用场景甚至比枚举思想还要多。当人脑遇到未知问题时，大多数人的第一直觉会从积累的“先验知识”开始，试图从“已知”中推断出“未知”，从而解决问题，说服自己。

其实这是一种递归算法的思想。递归思维的核心是从已知条件出发，逐步计算出问题的解。实现的方式很像我们初中数学试卷上的一系列“因为”和“所以”。那个时候，还是用三个点来表示的。

对于计算机来说，复杂的推导实际上是很难实现的。计算机擅长执行高密度和重复性的工作，但对于随机性和变化性高的问题则不容易计算。相比之下，人脑在推理不同维度的问题时具有更高的自由度。

例如，人脑可以很容易地从“太阳从东方升起”和“太阳从西方落下”推断出“太阳从东方升起”，进而大致推断出“现在的时间”。但这对计算机来说并不是那么容易，你可能需要设置一系列的约束来防止计算机从“南/北/东”和“落/飞/落”推“日/月/星”的可能性性别。

我说这个例子是为了说明，当计算机使用递归思维时，大部分都是重复推理。例如，从“今天是 1 号”到“明天是 2 号”。这种推理的结构非常相似，往往可以通过反复推理得到最终的解。

递归的思想可以用图形来表示，如下图所示。每次推导的结果都可以作为下一次推导的开始，这似乎和迭代递归的思想类似，但递归的范围更广。

案件

兔子问题。确定了一对大兔子每个月可以生出一对小兔子，每对新生的小兔子一个月后可以长成一对大兔子，并具备繁殖能力。如果不死，每生一男一女，问一年有几对兔子？

3 递归

说完递归，就不得不说它的兄弟思想——递归算法。两人也有“送”二字，可见两人还是有一定相似之处的。对“交付”的理解可以是循序渐进的，也可以是循序渐进的。在递归中，问题被连续推导，直到获得最终解决方案。在递归中，是连续的回归迭代，直到跳出回归。

递归算法实际上是将问题转化为更小的同类型子问题，先解决子问题，然后通过相同的求解过程逐步求解更高层次的问题，最后得到最终解。因此，与递归相比，递归算法的范围更小，并且要求子问题与父问题具有相同的结构。递归的思想在概念上没有这样的限制。

一句话描述递归算法的实现，就是在函数或子过程内部直接或间接调用自己的算法。因此，在执行过程中，最重要的是确定递归过程终止的条件，即跳出迭代过程的条件判断。否则程序会在自调用中无限循环，最终crash out memory。

递归算法的示意图如下图所示。显然，递归思维实际上是一个套娃过程。一般来说，政府严禁套娃。因此，在使用时，要明确“套娃”动作的止损条件，及时止损。

案件

河内塔问题。据印度传说，梵天创世时，他用金刚石和钢铁建造了三根柱子，其中一根自下而上叠放着64个金盘。梵天命令婆罗门将圆盘重新排列在另一根柱子上，从底部开始。并且规定小圆盘上不能放大圆盘，三列之间一次只能移动一个圆盘。

4 分而治之

分而治之。

分治算法的核心步骤是两步，一是分，二是治。但这也引出了一系列问题，为什么，如何划分，如何治疗，治疗后该怎么做。

分治算法很像向下管理的思想。它从最高层开始划分，将子任务划分为不同的子模块，然后划分大问题，细化系统问题的粒度，在最底层寻求最基本的解决方案。这种思路在很多领域都有应用，比如几何数学中的直角坐标、单位坐标、基等概念，都是通过将复杂问题简化为基本子问题，然后先求解子模块，再逐步求解。解决主要问题模块。

在实践中，分治算法主要包括两个维度的处理。一种是自顶向下，将主要问题逐层分解为子问题；另一种是自下而上，逐层增加子问题的解决方案。进入主要问题的解决方案。

那为什么要分呢？这是一个很好的解释。由于主要问题的规模太大，无法直接解决，因此需要对主要问题的粒度进行划分。

怎么分？继计算机最擅长的重复操作之后，划分出来的子问题需要相互独立，并具有与原问题相同的结构特征，以保证在解决了子问题后，主问题也可以顺势而为解决。

如何治愈？这涉及到最基本的子问题的解决。我们同意最小的子问题很容易解决，这样的子问题划分是有意义的。因此，最基础的子问题需要在治理过程中轻松解决。

治疗后怎么样？子问题解决了主要问题。在解决最基本的子问题时，需要逐层增加，逐步得到更高层次问题的解，直到得到原问题的最终解。

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

案件

合并排序。

5 动态规划

讲完分治，我们知道分治思想最重要的一点就是分解出来的子问题相互独立，具有相同的结构特征。并非所有问题都满足这一点。很多问题的划分子问题往往相互重叠，相互影响，因此很难使用分治算法有效、干净地划分子问题。

因此，动态规划。动态规划也需要将问题分成多个子问题，但子问题往往不是相互独立的。当前子问题的解决方案可以看作是对前几个阶段问题的完整总结。因此，在解决子问题的过程中需要进行多阶段决策，同时本阶段之前的决策可以构成一个最优的子结构。这就是所谓的优化原则。

最优化原则，一个优化策略具有这样的性质，即不管过去的状态和决策如何，对于前一个决策形成的状态，其余决策必须构成最优策略。同时，这样的最优策略是对已经做出的决策的总结，对后续决策没有直接影响，只能借用当前最优策略的状态数据。这也称为无后遗症。

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

动态规划的解决思路如下。在动态回归的开始，需要将问题按照一定的顺序划分为各个阶段，然后确定各个阶段的状态，比如图中节点的F0。然后重点是根据决策方法确定状态转移方程。即下阶段的状态需要根据当前阶段的状态来确定。

在这个过程中，下一个状态的确定往往需要参考上一个状态。因此，需要在每次状态转换过程中记录当前状态变量，以方便后续查找。

动态规划主要用于解决多阶段决策问题，但在实际问题中往往很难有统一的处理方法，必须根据问题的特点设计算法，这也是为什么这个算法很难真正掌握。

案件

背包问题。给定 n 个物品和一个容量为 m 的背包，给出这些物品的重量和价值。求解使装入背包的物品重量不超过背包容量且值最大。

6 贪婪

贪心算法，我想称之为最现实的算法思想。

人活在世上，不可能每一个选择都如此正确。有这么多问题，不可能找到所有问题的最佳解决方案。许多问题根本没有确切的解决方案，甚至没有解决方案。因此，在某些场景下，愚蠢地追求问题的最准确解决方案是没有意义的。

有人说，最好的解决办法还是有的。你不想要最好的解决方案吗？

是的，虽然很多问题都找不到最准确的解决方案，但确实会有一个或一些最优解决方案。但是我们必须追求这些最佳解决方案吗？我不这么认为。

算法的存在不仅仅是为了解决问题，更多的是提供一种“策略”。什么是“策略”、解决问题的方法、观点、方法。因此，贪婪的思想是有价值的。

回到贪心算法。从贪婪这个词我们可以看出，这个算法的目的是“贪得无厌”。但是，这种贪婪是“短视的”，使得贪婪算法无法放眼长远，只关注眼前利益。

具体来说，贪心算法在执行过程中，每次都会选择最大的利润，但总利润不一定是最大的。所以，这种傻傻想法的好处就是选择简单，不用纠结，不用考虑未来。

贪心算法的实现过程是从问题的一个初始解开始，每次都做出“当前最优”的选择，直到遇到一个局部极值点。贪婪带来的限制是显而易见的，即不能保证最终的解是最优的，很容易陷入局部最优的情况。

但是，它每次做出选择的速度都非常快，同时判断条件简单，可以比较快地给出类似的解决方案。这里的图表由下图表示。

此图表示多条线相交的解决方案。显然，下图中的直线是没有统一交点的，但是可以通过算法得到统一交点的最优解。如果使用贪心算法，那么在迭代过程中，每次都会选择最接近当前位置的线进行更新。这样，经过多次迭代，交点的位置就会在某个区域内无限跳跃。该区域也是可以得到的近似最优解区域​​。

案件

旅行商问题。给定一系列城市和每对城市之间的距离，找到访问每个城市一次并返回起始城市的最短线路。

7 回溯

尖甲绿，白露霜。所谓的伊拉克人民是在水边。从这里往回走，路又长又堵。来回旅行，就像在水中间一样。

每当提到回溯，就忍不住想起《建家》中的这首诗。看到心中思念的心上人，纵然路漫漫其修远兮，也情不自禁地逆流而上去追求她；回溯算法的过程就像追爱一样艰辛、反复，时而回溯，时而回溯。

回溯算法也可以称为启发式算法。是不是提醒你在女神面前小心谨慎？简单来说，回溯的过程就是在做出下一个选择之前测试每一种可能性；只有在有可能的情况下才继续前进，如果所有选择都不可能，则回到原来的位置，再次选择。

这样一来，回溯算法就很像一个进行中的枚举算法，在进行的过程中枚举和判断所有的可能性。常见的应用场景有遍历树结构、图结构、棋盘走法。

对于一个非常简单的示例，请参见下图。假设目的是从O0到O4，所有节点都需要回溯遍历路径。那么回溯算法的过程需要在前进的每一步测试所有可能的路径。

例如，O0 节点向前移动有 3 条路径，即上、中、下的 O1。回溯过程开始时，先到上面的O1，然后才能到上面的O2贪心算法 背包问题 c，但这是死路一条。然后需要从O2返回到O1，此时O1的唯一选择是行不通的，所以需要从O1返回到O0。然后继续测试中间的O1。

回溯算法的过程就是不断地进行这样的尝试、判断、撤退和重试，直到找到一条完整的前向路径。但是，在这个过程中，可以通过“剪枝”等约束来减少试探性搜索的空间贪心算法 背包问题 c，从而避免重复和无效的试验。比如O2节点上下，经过O0-O1-O2测试，已经验证了节点的不可行性，下一次就不需要从O1重复O2测试了。

回溯思维可以有效地用于解决许多大规模问题。回溯可以对复杂问题进行逐步调整，以便在过程中间遍历所有可能的枚举想法。这样，往往可以清楚地看到问题解决的层次，有助于更好地理解问题的最终解决结构。

案件

八皇后问题。将 8 个皇后放在一个 8×8 的棋格上，使它们不能互相攻击，即没有两个皇后可以在同一行、同一列或同一对角线上，并问有多少种方式。

8 模拟

与上述思路相比，仿真思路应该不难理解。

在很多实际场景中，由于问题规模大，变量太多，难以抽象出具体问题，无法根据抽象问题的特点设计算法。这时，模仿思维可能是最好的解决问题的策略。

模拟的过程就是尽可能地模拟真实的场景，然后利用计算机强大的计算能力来预测结果。这是一个比上述算法更宏大的想法。在真实场景的模拟中，系统组件的实现可能需要以上几种算法思想的参与。

模拟是一个非常虚幻的想法。没有具体的实现思路或具体的优化策略。只能说具体问题详细分析了。

应该怎么说明。我的理解是自定义的、任意的输入、不规则的系统响应，但只是为了得到一个可靠的理想输出。

9 总结

这种算法思维其实很神秘。同样的问题可以用不同的思路来实现。这八种念头并不像想象的那么独立。很多想法都混在一起，但角度和重点不同。以上案例不代表只能用一种思维来回答，只是用来体验对应的算法思路。

作为低级程序员，虽然不需要每天刷题，但还是需要有基本的算法思路。这种东西不是特定于算法，而是对系统或需求的更高层次的理解。