<aside>
💡 浙江大学算法设计MOOC笔记
</aside>
枚举
- 背景
- 找不到合适的数学公式和技巧
- （改良后）枚举复杂度不是特别大
- 通常用于找到一种情况使之满足题意的题目
- 配合假设法找到目标情形：假币问题
- 技巧
- 跳跃枚举法：跳过对没有必要的情况的枚举
- 局部枚举法：枚举局部，剩下的由该局部确定。例如熄灯问题
递归
- 作用
- 替代多重循环，如：n皇后问题。
- 这种类型往往要运用到一个
全局/静态变量来存储前面算过的结果，譬如n皇后就用到了一个全局数组来保存每一行的皇后拜访情况。全局/静态变量的好处就在于所有递归函数共享成果，就像递推迭代一样，每一步会影响下一步。
- 递归函数形式：T function( T f(n) )，函数意义：在前n-1步已经完成的情况下决定如何走第n步，往往第一个被调用的function参数为0或1（然后依次调用 $1$ ~ $n_0$）
- 解决实质是递归形式的问题
- 有些问题本身就是
递归定义的，比如不少表达式就是递归定义的：逆波兰，四则运算。逆波兰直接递归调用自身定义，四则运算则包含项，因子和表达式自身等多个概念，是一种间接递归调用自身定义
- 函数，数列的递推公式
- 关键是搞清楚问题是怎样递归定义的，可以借助画图，写代数式的办法捋清楚。
- 将问题分解为规模更小的子问题来求解
- 如何来分解？
“n=1+(n-1)”法
- 比方说要解决一个规模为n的问题，先找到解决该问题的
第一步怎么做，然后再把剩下的问题解决，剩下的问题规模刚好是n-1且解决过程自相似，可以用上递归n-1。e.g.台阶问题
“n=(n-1)+1”法
- 先解决n-1问题，再将最后一步完善,e.g.汉诺塔问题
- 与多重循环不同，该方法第一个调用的function参数往往时n0总规模
- 与分治不同，分治往往偏向于均分，而且多了一步综合，不过分治与递归又可以相互补充
<aside>
💡 附注
- atof（）函数，将浮点串转变为浮点数
- cin.peek（）函数，提前预知输入而非读取
- 浮点数的比较引入eps
</aside>
二分
- 简介
- 对一个待求系统（通常为有序系统），每次都均分为两半，通过判断“砍掉”其中“无用”的一半，对剩下的一半用同样的方法处理，直到得出结论。
- 作用
- 二分查找
- 不仅限于查找某一个具体的数，还可以查找符合某种要求的数（通常满足一定的大小关系）
- 二分法求方程根
分治
- 基本思想
- 将一个问题拆分成两个或两个以上规模更小的问题，然后将小问题分别解决或只解决
部分问题，最后综合处理一次。
- 一般模式：分划，局部处理，综合处理（分治 | 归并）
- 作用：使
规模缩小，提高算法效率（想想：不断地递归并分治，使得规模不断二分）
- 应用举例：基于分治策略的快速排序和归并排序
<aside>
💡 附注
- " x & 1 " 表达式判别x奇偶性
- 快速幂算法
</aside>
动态规划
- 背景
- 问题具有最优子结构
- 问题具有无后效性
- 当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取何种手段或经过哪条路径演变到当前的这若干个状态，没有关系。
- 单纯的递归会导致大量子问题 重复计算 时
- 思路方法
- 原问题分解为子问题
- 一些问题的求解归结于它的子问题的求解，且子问题与原问题类似，只是规模减小。
- 子问题一旦解决即被保存（通常存入一个多维数组）。
- 确定状态
- “状态”简介：在用动态规划解题时，我们往往将和子问题相 关的各个变量的
一组取值，称之为一个“状态”。一个“状态”对应于一个或多个子问题， 所谓某个“状态”下的“值”，就是这个“状态”所对应的子问题的解。
状态空间与时间复杂度：整个问题的时间复杂度是状态数目乘以计算每个状态所需时间。（在数字三角形里每个“状态”只需要经过一次，且在每个状态上作计算所花的时间都是和N无关的常数。）- 用动态规划解题，经常碰到的情况是，K个整型变量能 构成一个状态（如数字三角形中的行号和列号这两个变量 构成“状态”）。如果这K个整型变量的取值范围分别是 N1, N2, ……Nk，那么，我们就可以用一个K维的数组 array[N1] [N2]……[Nk]来存储各个状态的“值”。这个 “值”未必就是一个整数或浮点数，可能是需要一个结构 才能表示的，那么array就可以是一个结构数组。一个 “状态”下的“值”通常会是一个或多个子问题的解。
- 确定一些初始状态（边界状态）的值
- 确定状态转移方程
- 将第一步 分解 得到的原问题与子问题的关系用数学符号语言表述出来，即实现状态之间的转移关系。