算法和数据结构一直是程序员的基本功。可以说，没有数据结构的基础设施和算法的加持，就没有近80年的信息革命时代。数据结构可以看作是算法实现的容器。通过一系列具有特殊结构的数据集，可以更高效、更可靠地执行算法。算法的应用不仅仅体现在编程上。从狭义上讲，算法可以看作是数据传输和处理的顺序、方法和组成，就像各种排序算法一样。从广义上讲，算法更像是一种事物运行的逻辑和规则。太阳东升西落，海潮潮汐，月亮盈亏，都可以看作是一种算法，但执行者不是电子计算机，而是自然界万物。远谈。因此，要理解算法，重要的是领悟其思想，感受其内涵。可能有的同学会说，算法不就是Leetcode吗，不就是刷题吗？片面。问题总是层出不穷，而算法的思路却寥寥无几。所以，做了那么多题，还是不明白这些常见的算法思想，就该反思一下了。枚举首先，最简单的思想，枚举算法。枚举也叫穷举，顾名思义，就是穷举。枚举思想的应用场景非常广泛，也很容易理解。简单地说，枚举就是依次枚举出问题的可能性，然后将它们逐一带入问题测试中，从而从一系列可能的解中得到能够解决问题的准确解。枚举虽然看起来简单，但还是有一些容易被忽视的注意事项。例如，待解问题的“可能解/候选解”的筛选条件、“可能解”之间的相互影响、穷尽“可能解”的代价、穷举“可能解”的方法等。很多时候，没有必要在高层次上追求复杂的算法结构。相反，枚举的方法可以避免系统的复杂性带来的冗余，同时也可以在一定程度上减少篇幅。.枚举思路的过程可以用下图表示。通过实现预先确定“可能的解决方案”，然后在系统中一一验证，根据验证结果对“可能的解决方案”进行分析和论证。这是一种明显的结果导向思维，简单粗暴地试图从最终结果来分析“可能的解决方案”的可行性。但是，枚举思维的弊端当然也很明显。在实际运行的程序中，能直接用枚举法解决的问题很少。而当“可能解”的筛选条件不明确，导致无法准确判断“可能解”的数量和范围时，枚举就失去了意义。但是，当“可能解”的规模比较小，顺序验证的过程容易实现时，枚举的思想是一种方便快捷的方式。但在具体使用中，“可能方案”的验证也可以针对应用场景进行优化。这种优化可以从两个方向入手。一是简化问题，将需要处理的问题的模型结构尽量简化。这种简化具体可以体现在问题的变量个数上，减少变量的数据，从而从根本上减少“可能解”的组合。二是严格判断筛选“可能解”的范围和条件，尽可能剔除大部分无效“可能解”。话虽如此，一般来说，大多数无法枚举的场景都是因为“可能的解”数量众多，无法在有限的空间或有限的时间内完成对所有可能性的验证。但实际上，列举思想是最接近人的思维方式，更多时候是用来帮助我们“理解问题”而不是“解决问题”。案例：一百块钱买一百只鸡。问题描述如下：一只鸡值五块钱；一只母鸡三元，三只鸡一元。现在一百元需要买一百只鸡。公鸡、母鸡和小鸡各有多少只？递归思维和枚举思维一样，都是接近人类思维方式的思想，甚至比枚举思想在现实生活中有更多的应用场景。当人脑遇到未知问题时，大多数人的第一直觉是从积累的“先验知识”出发，尝试从“已知”中推导出“未知”，从而解决问题，说服自己。其实这是一种递归的算法思想。递归思想的核心是从已知条件出发，逐步计算出问题的解。实现方法很像我们初中数学试卷上的“because”和“so”系列。当时还是用三个点来表示。对于计算机来说，复杂的推导其实是很难实现的。计算机擅长执行高密度、高重复性的任务，但难以计算具有高随机性和可变性的问题。相比之下，人脑在推导不同维度的问题时具有更高的自由度。例如，人脑很容易从“太阳从东边升起”推导出“太阳从西边落下”，然后粗略推导出“现在的时间”。但是对于电脑来说就没那么容易了，你可能需要设置一系列的限制来避免电脑从“南/北/东”发射“太阳/月亮/星星”“坠落/飞走/坠落”的可能“性。我说这个例子是为了说明计算机在使用递归思维时，大部分是重复推理。例如，从“今天是1号”到“明天是2号”。这种推理的结构非常相似，往往可以通过反复推理得到最终的解。递归思想可以用图形表示，如下图所示。每次推导的结果都可以作为下一次推导的开始，这似乎与迭代递归的思想类似，但递归的范围更广。案例兔子问题。假设一对大兔子每个月可以生一对小兔子，每对刚出生的小兔子一个月后都能长成一对大兔子，具有繁殖能力。如果没有死亡，每次生一雌一雄，问一年有几对兔子？递归说完递归，我们就不得不说说它的兄弟思想——递归算法。两人还有一个“过”字，可见两人还是有一定相似度的。对“送”的理解，可以一一进行，循序渐进。在递归中，问题被逐次推导，直到得到最终的解。在递归中，就是一步一步的回归迭代，直到跳出回归。递归算法实际上是将问题转化为更小的同类问题，先求解子问题，然后通过相同的求解过程逐步求解更高层次的问题，最后得到最终的解。因此，与递归相比，递归算法的适用范围更小，要求子问题与父问题具有相同的结构。但是递归思维在概念上没有这样的限制。用一句话来描述递归算法的实现，就是在函数或子过程内部直接或间接调用自己的算法。因此，在实现的过程中，最重要的是判断递归过程的终止条件，即跳出迭代过程的条件判断。否则，程序会在自调用中无限循环，最终导致内存不足而崩溃。递归算法的示意图可以如下图所示。显然，递归思维其实就是一个套娃娃的过程。套娃一般是政府严禁的。因此，在使用时，一定要明确“套娃”动作的停止条件，及时止损。案例河内塔问题。起源于印度传说，梵天创造世界时，制作了三根金刚石柱，其中一根柱子上从下到上叠放着64个金盘。Brahma命令Brahmin将圆盘从下面按大小顺序重新排列在另一根柱子上。并且规定盘不能在小盘上放大，一次只能在三个柱子之间移动一个盘。分而治之，分而治之。分治算法的核心步骤是两步，一是分，二是治。但是这也引出了一系列的问题，为什么要分，怎么分，怎么治疗，治疗后怎么办。分治算法和向下管理的思想很相似。从最高层划分，将子任务划分到不同的子模块，进而可以拆分大问题，细化系统问题的粒度。最基本的解决方案在底部。这种思路在很多领域都有应用，比如几何和数学中的直角坐标、单位坐标、底的概念，都是把复杂的问题简化为基本的子问题，然后通过步骤逐步解决主要问题。首先解决子模块。模块。在实际应用中，分治算法主要包括二维处理。一种是自上而下，将主要问题逐层分解为子问题；另一种是自下而上，逐层增加子问题的求解。进入主要问题的解决方案。那为什么要分呢？这很容易解释。由于主要问题的规模太大，无法直接解决，因此需要对主要问题进行粒度划分。那怎么分呢？经过计算机最擅长的反复计算，划分出来的子问题需要相互独立，并且与原问题具有相同的结构特征。这样可以保证在解决了子问题之后，也可以解决主要问题。如何解决？这就涉及到最基本的子问题的求解。我们同意最小的子问题可以很容易地解决。只有这样划分子问题才有意义。因此，在处理过程中需要解决最基本的子问题。解决。接下来发生什么？子问题的解决是为主问题服务的。当最基本的子问题解决后，需要逐层递增，逐步得到更高层次问题的解，直到得到原问题的最终解。分而治之的思想示意图可以看下图。通过逐层粒度划分，将原问题划分为最小的子问题，依次得到更高粒度的解。从上到下，然后从下到上。先分解，再求解，再组合。案例合并排序。讲完动态规划中的分而治之，我们知道分而治之的思想最重要的一点就是分解后的子问题相互独立，具有相同的结构特征。不是所有的问题都能满足这一点。很多问题的子问题往往相互重叠、相互影响，因此很难用分而治之的算法有效、干净地划分子问题。于是乎，动态规划来了。动态规划也需要将问题分解成多个子问题，但子问题往往不是相互独立的。当前子问题的求解可以看作是对前几个阶段问题的完整总结。因此，这就需要在解决子问题的过程中进行多阶段决策，同时当前阶段之前的决策可以构成一个最优的子结构。这就是所谓的优化原则。最优化原理，一个最优策略具有这样的性质，即不管过去的状态和决策如何，对于前面的决策所形成的状态，剩下的决策一定构成最优策略。同时，这样的最优策略是对已经做出的决策的总结，对后续决策没有直接影响，只能借用当前最优策略的状态数据。这也称为无后效。动态规划是目前非常接近人类思维方式的一种算法。主要原因是人脑在计算过程中很难记住每一次决策的结果。在动态规划的实际运行中，往往需要额外的空间来保存每个阶段的状态数据，以供下一步决策使用。动态规划的求解思路说明如下。在动态回归开始的时候，需要把问题按照一定的顺序分成各个阶段，然后确定各个阶段的状态，比如图中节点的F0。然后重点是根据决策的方法确定状态转移方程。即需要根据当前阶段的状态来确定下一阶段的状态。在这个过程中，下一个状态的确定往往需要参考上一个状态。因此，需要记录每次状态转移时的当前状态变量，以方便后续查找。动态规划主要用于解决多阶段决策问题，但在实际问题中往往很难有统一的处理方法，算法设计必须结合问题的特点，这也是它难的原因才能真正掌握这个算法。案例背包问题。有n件物品和一个容量为m的背包，给出了物品的重量和价值。求解问题，使背包内物品的重量不超过背包的容量且数值最大。弹性贪心算法，我想称之为最现实的算法思维。人活在这个世界上，不可能每一个选择都那么恰到好处。问题这么多，不可能找到所有问题的最优解。很多问题根本没有准确的解法，甚至没有解法。所以在某些场景下，一味追求问题最准确的解决方案是没有意义的。有人说还是有最优解的。您不想要最佳解决方案吗？是的，很多问题虽然找不到最准确的解，但确实会有一个或几个最优解。但是我们必须追求这些最优解吗？我不这么认为。算法的存在不仅仅是为了解决问题，更多的是提供一种“策略”。什么是“战略”，解决问题的方法、角度、方法。因此，贪婪的思考是有价值的。回到贪心算法。从greedy这个词我们可以知道这个算法的目的是“贪多”。但这种贪心是“短视”的，这使得贪心算法无法着眼长远，只注重眼前利益。具体来说，贪心算法在执行过程中每次都会选择收益最大的，但总收益不一定是最大的。所以这样傻甜甜的想法的好处就是选择简单，不用纠结，不用考虑未来。贪心算法的实现过程是从问题的一个初始解开始，每次都做出“当前最优”的选择，直到遇到局部极值点。贪心带来的局限性很明显，就是不能保证最终的解是最优的，容易陷入局部最优的情况。但它每次做出选择的速度都非常快，同时判断条件简单，能够比较快地给出相似的解。这里的示意图用下图表示。此图表示多条直线相交的解决方案。很明显，下图中的直线没有统一交点，但是可以通过算法得到统一交点的最优解。如果使用贪心算法，那么在迭代时，每次都会选择距离当前位置最近的直线进行更新。这样，经过多次迭代，交点的位置就会在某个区域无限跳跃。而这个区域就是可以得到的近似最优解区域??。案例旅行商问题。给定一个城市列表和每对城市之间的距离，找到访问每个城市一次并返回起始城市的最短路线。回头看，芦苇青，白露霜。所谓伊拉克人在水这边。从中回溯，路漫漫其修远兮。从中回溯，宛在水中。每当提到回溯，我都会不由地想起《间甲》中的这首诗。看到心心念念的心上人，即使路漫漫其修远兮，也忍不住逆流而上去追求；而我继续往下游寻找，感觉她好像就在河中央。回溯算法的过程就像追爱一样艰辛、反复，时而回溯，时而回溯。回溯算法也可以称为启发式算法，有没有提醒你在女神面前要小心。简单地说，回溯的过程就是在做出下一个选择之前测试每一种可能性；只有存在这种可能性才会往前走，如果所有的选择都是不可能的，那就回到原来的位置，重新选择。从这个角度来看，回溯算法很像一个不断进行的枚举算法，在这个过程中对所有的可能性进行枚举和判断。常用的应用场景是树结构遍历、图结构遍历、棋盘走法。有关一个非常简单的示例，请参见下图。假设目标是从最O0到O4，需要对所有节点进行回溯遍历路径。然后回溯算法的过程需要在向前的每一步都测试所有可能的路径。例如O0节点前进的路径有3条，分别是O1的上、中、下路径。回溯过程开始时，先到上层O1，然后才能到达上层O2，但此时是死胡同。那么就需要从O2返回到O1，而此时O1唯一的选择是不可行的，所以需要从O1返回到O0。然后在中路继续试探O1。回溯算法的过程就是不断地进行这样的探测、判断、返回和重新探测，直到找到一条完整的前向路径。只是在这个过程中，可以通过“剪枝”等限制来缩小试次搜索空间，避免重复无效试次。比如对于上下O2节点，经过O0-O1-O2的测试，已经验证了该节点的不可行性，下次就不需要从O1重复测试O2了。回溯的思想可以有效地运用在很多大规模问题的求解中。回溯可以逐步调整复杂的问题，使中间过程遍历所有可能的枚举思路。这往往可以清楚地看到问题解决的层次，有助于更好地理解问题的最终解决方案结构。案例八皇后区问题。在一个8×8的方格棋子上放置8个皇后，使它们不能互相攻击，即任意两个皇后不能在同一行、同一列或同一斜线上。有多少种玩法。与上述思维相比，模拟思维的理解应该不难。在很多实际场景中，由于问题规模大、变量过多等因素，很难对具体问题进行抽象，无法根据抽象问题的特点设计算法。这时候，模拟思维可能是最好的解题策略。模拟过程就是尽可能地模拟真实场景，然后通过计算机强大的计算能力来预测结果。这是一个比上述算法更雄心勃勃的想法。在真实场景的模拟中，系统组件的实现可能需要上述算法思想的参与。仿真是一个很空想的想法，没有具体的实现思路，也没有具体的优化策略。只能说具体问题具体分析。应该如何说明？我的理解是自定义的，任意的输入，不规律的系统响应，却只是为了获得可靠的理想输出。总结算法思维其实很虚幻。同样的问题可能用不同的思路来实现。这八个念头并不像想象的那么独立。很多想法混杂在一起，只是角度和侧重点不同。以上案例并不是说只能用一种思维来回答，只是用来体验对应的算法思维。作为一个底层程序员，虽然不用天天刷题，但是还是需要有基本的算法思路。这种东西不是特定于某个算法，而是在于对系统或需求有更高层次的理解。喜欢独立精神，自由思考。
