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

</aside>

<aside>

枚举

• 背景

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

• 技巧

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

</aside>

<aside>

分治

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

二分

<aside>

• 二分法求方程根

• 二分查找

  • 不仅限于查找某一个具体的数，还可以查找符合某种要求的数（通常满足一定的大小关系）

• 对一个待求系统（通常为有序系统），每次都均分为两半，通过判断“砍掉”其中“无用”的一半，对剩下的一半用同样的方法处理，直到得出结论。 </aside>

• 红蓝染色法：二分查找 红蓝染色法【基础算法精讲 04】_哔哩哔哩_bilibili

  • 循环不变量：[0, left) and [right, n)
    • 左区间元素<target，右区间元素≥target
    • 根据 a[(left + right) / 2]的值判断更新左区间范围还是右区间范围

• 边界问题均可以转化为邻接值的lower_bound的问题

  • lower_bound(x) = i ⇒ [i, n) ≥ x
  • first index which a[i] ≥ x = lower_bound(x) ⇒ [[
  • first index which a[i] > x = lower_bound(x+1) ⇒ ([
  • last index which a[i] ≤ x = lower_bound(x+1)-1 ⇒ ][
  • last index which a[i] < x = lower_bound(x+1)-1 ⇒ )[

递归与回溯

递归函数

<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皇后，解数独等等

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