总结四大算法联系与区别
以下内容为教材：王晓东《计算机算法设计与分析（第五版）》
算法概述
有人突然问你，什么是算法？
答：算法是能解决一系列问题的清晰指令，能对一定范围的输入，在有限的时间内获得所求的输出。
算法满足的四个性质是什么？
有输入
有输出
确定性，没有歧义指令
有限性，时间有限。
什么是递归算法？
直接或间接调用自身的算法
分治思想是什么?
把一个大的问题分成若干个子问题，这些子问题相互独立但是又和原问题相同。分治就可以递归的解决这些子问题，然后将这些子问题的解合并，得到原问题的解。
归并排序的思想是什么？
将带排序的序列分成大小大致相同的两个子序列，分别对两个子序列进行排序，最终将排序好的子序列合并。
动态规划的思想是什么？
和分治法类似，都是将问题分解成若干个子问题，先求子问题，再结合子问题得到原问题的解，但是动态规划的子问题不是相互独立的，他们之间是有依赖关系的。
贪心算法和动态规划的联系是什么？
相同点：都具有最优子结构
不同点：选择性质，贪心算法只是在局部做最优选择。
贪心选择性质是什么？
所求问题的整体最优解可以通过一系列局部最优的选择来达到。
这就是它和动态规划的主要区别。
贪心和动态规划的区别？
贪心算法所做的贪心选择可以依赖以往所做的选择但决不依赖将来所做的选择，也不依赖子问题的解。正是由于这种差别，动态规划算法通常以自底向上的方式解决每个子问题，而贪心算法通常以自顶向下的方式进行。
最优字结构性质是什么？
一个问题的最优解包含子问题的最优解，就是具有该性质。
为什么贪心算法不适用于01背包问题？
贪心无法保证最终能把背包装满，一部分闲置的空间让每千克背包的空间价值降低了。
在考虑01背包问题的时候，应该比较选择物品和不选择这个物品所导致的最终方案，再做出更好的选择。
回溯法的基本思想
我以自己的方式表达：
以深度优先的方式搜索整个解空间。来到一个解的节点之后修改状态并继续递归搜索，在此节点上递归结束并回到当前解的节点之后将当前修改了的节点状态恢复。并以此搜索完整个解空间。
分支限界法和回溯法的区别
回溯法是dfs，分支限界法是bfs、或者最小耗费优先。
分支限界法的搜索策略是什么？
（看了书之后的个人理解）相当于把广度优先搜索用的那个队列改成了优先队列，出队列的时候是出优先级最高的元素。又有点像二维数组A*寻路算法一样。这和以前看到视频弹幕里有人说dfs+剪枝就是分支限界法还不太一样。
书中提到：产生儿子节点的时候，导致不可行解或者导致非最优解的儿子节点被舍弃，这一点倒是还挺像剪枝的。
图片链接：https://s1.ax1x.com/2022/08/12/vJpXL9.png
请于2022年12月之后再盗此图。
算法启示录
短作业优先：手头上有很多任务，如果突然来了一个更紧急的任务就先去做更紧急的。紧急的做完了就继续做不那么紧急的任务。
广度优先学习：泛泛的学习，学这个语言那个语言，这个技术那个技术。也可以通过这个来回忆知识结构树。
深度优先学习：学这个语言遇到一点不会的就深挖，发现需要解决疑问a，b，c，解决疑问a又要去解决a1, a2..。也应用于在房间里找钥匙，手动在文件夹里找一个文件。
所以学习，如果只bfs就会不深入不精通，会被面试官pass，如果只dfs就容易消磨斗志，学习速度下降，缺少新鲜感。学习要bfs和dfs结合
动态规划未来：自底向上，根据自己曾经的履历和成就来决定自己的下一步。dp[i]＝func(dp[i-1]…)，缺点是容易发生较大变化，比较随性。大一上学期之所以决定走设计方向是因为高考后的暑假喜欢学adobe做东西，大一下之所以又决定走编程方向，是因为大一上发现自己编程还可以，又喜欢编程了。优点是前进动力更大，迭代性更好。
分治：把回家这件繁琐事情分成很多段，每段还可以分成好几个小段。（一般现实生活中不会分太多），先从学校到学校所在省，再从学校省到家的省，再从家的省到家。然后再细分下去。学校到学校附近车站，车站到火车站，火车站到地铁…
递归，分治出来的东西具有相同的子结构，每日总结，每周总结，每月总结，每年总结。
二分查找：发现单词不会翻字典的时候，看视频拨动进度条的时候。
贪心算法：找对象，贪着贪着发现最终什么都没贪到。（误）
计入哈希表：其实在看数学书的时候，把常用的公式记录在扉页，做题翻书找公式不用再一页一页找了，直接看扉页。就是类似这样的思想。
插入排序：和别人打牌的发牌阶段自己整理自己的牌
记忆化搜索：经过一番大力的网上搜索搜到自己要解决的技术问题的时候，把这个问题保存在自己的博客里或者笔记里。以后再遇到问题先看看自己的笔记里有没有。
