数据结构_递归、回溯、分治、动态规划
一、递归
递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。
本文主要从以下方面进行介绍递归算法：
1. 递归算法的概念
2. 递归算法的特点
3. 递归算法的应用
4. 递归算法的典型实例
1. 递归算法的概念
递归过程一般通过函数或子过程来实现。递归方法：在函数或子过程的内部，直接或者间接地调用自己的算法。
2. 递归算法的特点
2.1 递归的特点
(1) 递归就是在过程或函数里调用自身，分别称为直接递归和间接递归；
(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口；
(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低；
(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。鉴于（3）（4）特点，所以一般不提倡用递归算法设计程序。但是有些问题必须用递归解决。
2.2 递归的要求
递归算法所体现的“重复”一般有三个要求：
（1）每次调用在规模上都有所缩小(通常是减半)；
（2）相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；
（3）在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。
3. 递归算法的实现
3.1 递归的设计思路
（1）确定递归公式
（2）确定边界(终了)条件
3.2 递归的设计模式
procedure aaa(k:integer);
begin
if k=1 then (边界条件及必要操作)
else begin
aaa(k-1);
(重复的操作);
end;
end;
4. 递归算法的典型实例
4.1 上楼问题/斐波那契数列
问题描述： 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.
问题分析：设n阶台阶的走法数为f(n)
显然有
f(1) = 1;
f(2) = 2;
f(n)={f(n-1)+f(n-2)} n>2
递归结束条件： n = 1;
算法实现见链接：https://blog.****.net/sunjinshengli/article/details/53461837
二、回溯
概述
回溯算法是一种组织搜索的一般技术，它常常可以避免搜索所有的可能性，适用于求解那些有潜在的大量解但是有限个数的解已经检查过的问题。
3着色问题
问题描述
给出一个无向图G=(V,E)，需要用三种颜色之一为V中的每个顶点着色，要求没有两个相邻的顶点有相同的颜色。
算法思想
我们称没有两个邻接顶点有同样颜色的着色方案为合法的，反之成为非法的。如果不考虑合法性的要求，给出n个顶点的无向图，将其用三种颜色着色，共有n^3种不同的方法，因为没一个顶点都有三种不同的着色方案，这就构成了一颗三叉树，如图：
在该三叉树中，从根到叶子节点的每一条路径代表一种着色方法（合法的和不合法的），我们需要做的就是选出一条合法的从根到叶子的路径即可。所以我们从跟节点开始向叶子节点走，这时有两种情况：
从根到当前节点的路径对应一个合法的着色：
当前路径长度小于n：过程终止（除非希望找到不止一种着色方案）
当
前路径长度等于n：生成当前节点的一个子节点，并将生成的当前节点的子节点标记为新的当前节点
从根到当前节点的路径对应一个非法的着色：回溯到当前节点的父节点即将当前节点的父节点标记为新的当前节点
代码
使用数组c[1…n]代表图的顶点集合，判断合法性只需判断与当前有联系的点中是否存在与之涂色相同的点即可，此处为节省时间省略该部分代码的实现。
代码实现见链接：https://blog.****.net/qq_36982160/article/details/80205879
三、分治
分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。递归！
分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
分治法所能解决的问题一般具有以下几个特征：
1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；
第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、
第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。
第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
分治法求解的经典问题：
（1）二分搜索
（2）大整数乘法
（3）Strassen矩阵乘法
（4）棋盘覆盖
（5）合并排序
（6）快速排序
（7）线性时间选择
（8）最接近点对问题
（9）循环赛日程表
（10）汉诺塔
汉诺塔问题
在汉诺塔游戏中，有三个分别命名为A、B、C得塔座，几个大小各不相同，从小到大一次编号得圆盘，每个原盘中间有一个小孔。最初，所有得圆盘都在A塔座上，其中最大得圆盘在最下面，然后是第二大，以此类推.
这个问题的思维其实可以从顶向下入手，现在123都在C上了，只需要把4放到B上，再把123放到B上即可。那么现在问题变成了如何把123放到C上，其实发现，这和原问题是同样的问题，只不过辅助柱从C变成了B。因此，按照分治的思想，把一个大问题逐渐拆解成小问题，最终采用递归的方式解决。
-
func: -
if n!=0 then ;预定值 -
func(n-1, a, c, b) ;将n-1个盘子由a移动到b，以c为辅助柱子（注意参数顺序） -
move a[n] to c ;将a上的最后一个盘子移动到c -
func(n-1, b, a, c) ;将n-1个盘子由b移动到c，以a为辅助柱子 -
endif ;完成
四、动态规划
“某种程度上，动规是贪心的泛化，贪心是动规的特例。”
动规：大爆搜
贪心：把大爆搜剪枝剪到只有一条
贪心是求局部最优，以得到全局最优（不一定是正确的，需要证明）
dp是通过一些状态来描述一些子问题，然后通过状态之间的转移来求解（一般只要转移方程是正确的，答案必然是正确的）
贪心着眼现实当下，动规谨记历史进程。
https://blog.****.net/jarvischu/article/details/6056387
借鉴这位博主的话
相同：
动态规划和贪心算法都是一种递推算法
均有局部最优解来推导全局最优解
不同点：
贪心算法：
1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。
2.由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。
动态规划算法：
1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解
2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解
3.边界条件：即最简单的，可以直接得出的局部最优解
在动态规划之前要分析能否把大问题分解成小问题，分解后的小问题也存在最优解，如果把小问题的最优解组合起来能够得到整个问题的最优解。
动态规划的四个特点
求一个问题的最优解(通常是最大值或最小值)
该问题能划分为若干个子问题
子问题之间还有重叠的更小的子问题
由于子问题在分解大问题的过程中重复出现，为了避免重复求解子问题，我们可以从下往上的顺序先计算小问题的最优解并存储下来，再以此为基础求取大问题的最优解。从上往下分析问题，从下往上求解问题。
---------------------
本文参考资料及学习链接：
【1】算法-递归算法：https://blog.****.net/sunjinshengli/article/details/53461837
【2】回溯算法：https://blog.****.net/qq_36982160/article/details/80205879
【3】五大算法之分治算法和动态规划算法：https://blog.****.net/weixin_33547926/article/details/82666634
【4】动态规划和贪心：https://blog.****.net/u013164931/article/details/79844880