递推 & 递归 & 习题课
欢迎参考算法基础课的DFS笔记
递归
递归搜索题的做题步骤
1. 把搜索问题的顺序变成搜索树
2. 把搜索树转化成代码，核心就是考虑 dfs() 的参数（全局 or 形参，需要多做题积累经验）
AcWing 93. 递归实现组合型枚举
与排列型枚举的区别：组合型不考虑顺序，只要数相同就算相同
- 方法：递归搜索树
- 关键：防止重复枚举
- 人为规定组合数的顺序，比如从小到大排列
- 局部保证升序枚举，也就是保证新加的数大于前一个数
- 规定顺序后不需要使用判重数组或参数
- 优化：剪枝，提前判断当前节点是否有解，没有就直接退出，不进行进一步递归
代码
AcWing 1209. 带分数
$$n=a+\frac{b}{c}$$
暴力做法
- 递归枚举全排列
- 枚举 $a b c$ 的位数（只用枚举 $a$ 和 $b$ 的位数即可）
- 转化成带分数，判断是否满足题意
优化：利用 $n$
- 原式转化为 $$cn=ca+b$$ 因此可以只枚举 $a$ $c$ ，$b$ 可以直接算出来
- 枚举 $a$ 的所有可能是，如果 $a\geq n$ 就可以直接剪枝
- 步骤就是先枚举 $a$ ,再枚举 $a$ 的节点枚举 $c$ ，最后判断 $b$ 是否满足条件
时间复杂度：$O(n!\times n)$
- 暴力 $$9!\times 9\times C^{2}_{8}<10^{8}$$
优化之后运行时间是暴力的 $\frac{1}{4}$
优化代码
递推
递归自顶向下呈树状，把大问题分成几个小问题来解决
递推自底向上呈线性，先解决小问题，再用小问题的答案解决大问题
AcWing 717. 简单斐波那契
经典中的经典
代码
AcWing 95. 费解的开关
性质
1. 步骤顺序任意，因为最终每一个灯的状态是由这个灯和周围的灯开关的次数决定的
2. 每个灯最多被开关一次，因为开关两次相当于不操作
3. 按行枚举操作，每一行开关的操作完全被上一行灯的亮灭状态决定，因为上一行要全亮，只能由当前行来操作；意味着只要第一行的操作确定后，每一行的操作都是确定的
因此只用枚举第一行操作，之后判断最后一行是否全亮（合法）
通用模型 & 解法
给出某个初始状态和目标状态，再给出一些操作，然后问最少需要进行几步可以把初始状态变为目标状态
一般方法：BFS,但时间复杂度高，只适用于局面很小时
局面大时需要考虑其他更快的解法
时间复杂度
$$32\times 25\times 5\times 500=2\times 10^{6}$$
