<aside> 💡 浙江大学算法设计MOOC笔记 + 代码随想录思考

</aside>

<aside>

枚举

• 背景

  • 找不到合适的数学公式和技巧
  • （改良后）枚举复杂度不是特别大
  • 通常用于找到一种情况使之满足题意的题目
  • 配合假设法找到目标情形：假币问题

• 技巧

  • 跳跃枚举法：跳过对没有必要的情况的枚举
  • 局部枚举法：枚举局部，剩下的由该局部确定。例如熄灯问题

</aside>

<aside>

分治

• 基本思想
  • 将一个问题拆分成两个或两个以上规模更小的问题，然后将小问题分别解决或只解决部分问题，最后综合处理一次。
• 一般模式：分划，局部处理，综合处理（分治 | 归并）
  • 常常与递归思想结合
• 作用：使规模缩小，提高算法效率（想想：不断地递归并分治，使得规模不断二分）
• 应用举例：基于分治策略的快速排序和归并排序 </aside>

<aside>

二分

• 对一个待求系统（通常为有序系统），每次都均分为两半，通过判断“砍掉”其中“无用”的一半，对剩下的一半用同样的方法处理，直到得出结论。
• 二分查找
  • 不仅限于查找某一个具体的数，还可以查找符合某种要求的数（通常满足一定的大小关系）
• 二分法求方程根 </aside>

递归与回溯

递归函数

<aside>

替代多重循环，如：n皇后问题。

• 这种类型往往要运用到一个全局/静态变量来存储前面算过的结果，譬如n皇后就用到了一个全局数组来保存每一行的皇后拜访情况。全局/静态变量的好处就在于所有递归函数共享成果，就像递推迭代一样，每一步会影响下一步。
• 递归函数形式：T function( T f(n) )
  • 函数意义：在前 n-1 步已经完成的情况下决定如何走第 n 步，往往第一个被调用的函数参数为 0 或 1（然后依次调用 $1$ ~ $n_0$） </aside>

<aside>

解决实质是递归形式的问题

• 有些问题本身就是递归定义的，比如不少表达式就是递归定义的：逆波兰，四则运算。逆波兰直接递归调用自身定义，四则运算则包含项，因子和表达式自身等多个概念，是一种间接递归调用自身定义
• 函数，数列的递推公式
• 关键是搞清楚问题是怎样递归定义的，可以借助画图，写代数式的办法捋清楚。 </aside>

分解子问题

• “n=1+(n-1)”法
  • 比方说要解决一个规模为n的问题，先找到解决该问题的第一步怎么做，然后再把剩下的问题解决，剩下的问题规模刚好是n-1且解决过程自相似，可以用上递归n-1。e.g.台阶问题
• “n=(n-1)+1”法
  • 先解决n-1问题，再将最后一步完善，例如：汉诺塔问题
• 与多重循环不同，该方法第一个调用的function参数往往为n0总规模（整个搜索空间）
• 与分治不同，分治往往偏向于均分，而且多了一步归并，不过分治与递归又可以相互补充

<aside> 💡 附注

1. atof函数，将浮点串转变为浮点数
2. cin.peek函数，提前预知输入而非读取
3. 浮点数的比较引入eps </aside>

回溯法

一般可以解决如下几种问题：

• 决策树问题：能否用一颗决策树的step-by-step方式搜索到 Solution？
• 组合问题：N个数里面按一定规则找出k个数的集合
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后，解数独等等

回溯法的解题模板大致如下：路径+递归函数+中间结果

 class Solution {
	public:
		vector<int> path; // 回溯路径
		int value; // 中间结果
		vector<int> solutions; // 保存结果
		
		// 递归决策函数
		void choose(vector<int> &searchSpace, int start) {
			// 终止判别
			if (done(start)) {
				solutions.push_back(value);
				return;
			}
			
			// 同层决策循环
			for (int i = start; i < searchSpace.size(); i++) {
			  if (!prune(i)) { // 剪枝
				  // 保存
					path.push_back();
					update(value);
					// 递归
					choose(searchSpace, i + 1);
					// 回溯
					resume(value);
					path.pop_back();
				}
				
			vector<int> solve(vector<int> &searchSpace) {
				int start; // 搜索起始点
				initialize(path, value, start);
				choose(searchSpace, start);
				return solutions;
 }

动态规划 DP

<aside>

什么问题适合用 DP？

• 问题具有最优子结构
  • 问题的最优解所包含的子问题的解也是最优的
• 问题具有无后效性
  • 当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取何种手段或经过哪条路径演变到当前的这若干个状态，没有关系。
• 单纯的递归会导致大量子问题重复计算时 </aside>

<aside>

DP 程序写法

<aside>

记忆递归型

递归函数+记忆数组

</aside>

<aside>

“人人为我”递推型

1,2,3,...,n-1 => n

递推到“n”时“n”仍未被求出，前面已被求出的状态值用于求“n”的状态值

</aside>

<aside>

</aside>

</aside>