这是算法课上的一次总结与分享。

分治

分治也就是分而治之，关于分治老师已经讲了很多，但是为什么这样做可以有效的解决问题？

以我们思考问题为例。假设当遇到一个问题时，我们会习惯性想一下子搞定这个问题，直接从输入到输出 ， 如 1 + 1 = 2 ，不用思考这个模型烂熟于心。

但是遇到了一个问题发现搞不定，感觉很难，无法直接从输入到输出这个时候才会考虑分治。分解成一个个小问题，也就是直接的输入到输出类型的知识。解决小问题最终解决大问题！这样做显然很有用。

if (是否存在类似模型):
    套模型 (直接从输入到输出的知识)
else: 
    分而治之

举个例子：你看到了一个很好看的网站，你想做一个类似的网站，怎么解决做网站这个大问题，经过思考后发现这个不是我可以像 1 + 1 一样 直接输入到输出 的简单问题。一下子做不成一个网站（当然你能直接做好的话当我白说🙃）然后发现好难啊！这个时候才会去思考分解问题，网站分为前端 + 后端，然后再拆开去看需要学什么 balabalab… 这是正常思考问题的过程，很难的问题大都会先思考这个问题我之前遇到过没，不行的话再采用分治来解决。

假设当前的我只会 3 种知识并且遇到了一个我一定可以解决的问题，这些知识可以直接从输入到输出，但是这三种知识排列组合后会形成 7 种新的直接输入到输出的知识，这是一个解空间。我们从这 7 种知识种检索发现其中一种知识可以解决我们遇到的问题，然后这个问题解决了。

但是当我们会 20 种知识的时候，这些知识的排列组合会形成 1048575 种新的知识，我们习惯性的会从这里面检索能够解决问题的一种。但是这个解空间太大了是指数级别的。并且实际问题中我们会的知识远远多于 20 种，这就是为什么编程难的原因。

但是分治法呢，只需要了解问题是由哪些知识组成，挨个解决，一步一步的解决，而不是那种直接的输入输出，这将一个指数级别的问题降低到了线性。

贪心

我认为贪心就是朝着某个方向不断的前进，最终的得到一个结果，但是这个结果是否是整体最优的，这个有些情况下是，但是有些情况下不是。

贪心在于贪心策略的选择，也就是怎么选择方向。例如活动安排问题，一段时间内存在很多活动，如何选择才尽可能多的安排更多的活动。

我们想要安排尽可能多的活动，那么问题就变成了活动的时长尽可能短且活动与活动之间不冲突，也就是兼容的活动。

有三个方向：

• 按开始时间排序。 假设一种极端情况，一个会从头开到尾，显然不合适。
• 按时间短且兼容的活动排序。 假设这个会开始的时间很完，但是他之前的时间显然浪费掉了。也不合适。
• 按结束时间排序。 结束时间早说明时间短而且冲突小，可以按这个来排序。

例如 0/1 背包问题和背包问题，这两个问题区别很大，我认为本质在于物体是否可分割。可分割怎么来定义，就像背包里面装的是大米随便怎么拿，反之像古董这些东西不能敲碎放进去。如果可以分割的话那么用贪心就可得到最优解。

但是如果是不可分割，贪心就不可以了，容易陷入局部最优的情况，就像人生每一步一样踩下的每一步都是当前最好的选择，但是却并不能达到更高的境界。模拟退火算法引入一些不确定性，可以避免陷入局部最优的情况，SGD 里面的引入动量的概念也避免了局部最小值。

动态规划

动态规划的本质是搜索！动态规划的本质是数学归纳法！

这个好难，主要是动态转移方程，好多题看答案都是一看就会，一写就废的那种。

把递归树画出来，然后找规律，

KMP 里面有动态规划的感觉，

总结

以上的这些算法思想都有很多常见且经典的例题，总结这些例题后可以建立起对应的模型，刷题也是不断建模的过程。

通过学习以上的算法中体现出的模型，可以使得我们将这些模型变成直接的输入输出性的知识！下次遇到就可以直接套用。

但是更多的还是未知的问题，如何解决？

我认为更重要的是总结出模型中的共性，也就是泛化的能力！