算法复习

算法设计思想与状态空间

基础概念

• 判定问题、优化问题
• 优化问题都可以表示为判定问题

状态与状态空间

• 状态（s）
• 状态转移（t）
• 状态空间（S）：状态（点）与状态转移（边）构成的图
• 状态变量（v）：变量的不同取值表示状态的变化
• 价值函数（f）：​f: v \rightarrow x，将状态变量映射到值

可计算问题的本质

• 判定问题：初态与目标状态是否可达
• 优化问题：初态转移至目标状态的最优价值

搜索算法——状态空间遍历算法

• DFS：判定或统计；递归或栈；运行时间、递归开销
• BFS：求最少转移次数；队列；内存消耗

状态压缩

• 利用二进制等，压缩状态变量，减少存储空间占用
• 利用位运算等，加速状态转移，减少时间消耗
• 状态哈希：​H:X\rightarrow Y,\ where\ |X|=n, y_i\in [0,n)

搜索算法

• 八数码问题：

  • 状态压缩：康托展开，​a_i 表示 ​count(j > i, v_j < v_i)
    X = \sum_{i=1}^n a_i(n - i)
  • 双向广搜

• 埃及分数问题：

  • 迭代加深搜索：搜索深度作为状态变量的一部分（优化问题 —> 判定问题）

搜索算法的优化

• 缩小状态空间
• 避开不必要的状态转移（动态规划、分治、贪心）

动态规划

• 在搜索过程中，对于已搜索过、价值函数不会再更新的状态，通过记忆化的方式，避免重复搜索。

使用动态规划的必要条件

• 最优子结构：最优解可以由子问题的最优解（或部分状态的最有价值函数）构造得出。
• 重叠子问题：一些子问题（或状态）在搜索中会重复遇到。
• 无后效性：子问题最优解一旦确定就不会再被更新。

难点

• 价值函数的设计
• 状态转移时价值函数的更新方式

关键

• 定义状态和价值函数（建模）
• 确定初态和对应价值（边界）
• 确定状态转移时价值函数的更新方式（状态转移方程）

两种实现方式

• 记忆化搜索：自顶向下
  • 状态：形参
  • 状态转移：函数调用，通过实际传入参数
  • 价值函数：函数的返回值，须记录
• 打表法：自底向上
  • 状态：数组下标
  • 状态转移：数组元素间的递推关系
  • 价值函数：数组的值

常见类型

一维递推问题（求和类）

• 爬楼梯、斐波那契数列 ​O(n)
• 优化方式：矩阵快速幂 ​O(logn)

一维递推问题（最值类）

• 最长上升子序列

  • 状态：​f(i) 表示第 ​i 个数作为结尾的最长上升子序列的长度。

  • 状态转移方程：

    f(i) = a\max_{1\le j\lt i}\{\delta(a_i\gt a_j)f(j) + 1\}

  • 边界与答案：

    f(1)=1;\ \max_{1\le i\le n}\{f(i)\}

  • 时间复杂度：​O(n^2)

• 优化方式：

  • 单调队列 / 栈

    f(i) = \min_{i-k\le j\lt i}\{f(j)\}+g(i)

  • 斜率优化

    f(i) = \min_{1\le j\lt i}\{g(j)+b(j)*a(i)\}+w(i)

二维问题——区间问题

• 回文子序列的个数

  • 状态：​f(i,j) 表示区间 ​[i,j] 之间的回文子序列个数
  • 状态转移方程：
    f(i,j)=f(i+1,j)+f(i,j-1)-\delta(s_i\ne s_j)f(i+1,j-1)+\delta(s_i=s_j)
  • 边界与答案：
    f(i, i)=1;\ f(1,n)
  • 时间复杂度：​O(n^2)

• 最优矩阵链乘法

  • 状态：​f(i, j) 为 ​[i,j] 间的最快方案
  • 状态转移方程：
    f(i,j)=\min_{i\le k\lt j}\{f(i,k)+f(k+1,j)+r_ic_kc_j\}
  • 边界与答案：
    f(i, i)=0;\ f(1,n)
  • 时间复杂度：​O(n^3)

• 优化方式

  • 四边形不等式优化

    f(i,j)=\min_{i\lt k\le j}\{f(i,k-1)+f(k,j)+w(i,j)\}

• 区间最值查询：查询 ​[l,r] 区间内最值，有 ​m 次查询

  • 状态：​f(i,j) 为以 ​i 为起点，长度为 $2^j$ 的区间最值（倍增）

  • 状态转移方程：

    f(i,j)=\min\{f(i,j-1),f(i+2^{j-1},j-1)\}

  • 边界与答案：$2^s ​ 超过 [l,r]$ 区间长的一半

    f(i,0)=a_i;\ let\ s=\lfloor \log(r-l+1)\rfloor,\ \min\{f(l,s),f(r-2^s+1,s)\}

  • 时间复杂度：​O(n\log n+m)

二维问题——序列间比较问题

• 编辑距离：​A\mathop\longrightarrow\limits^{插、删、替} B 最少次数

  • 状态：​f(i,j) 为使 ​A 的长度为 ​i 的前缀与 ​B 的长度为 ​j 的前缀通过编辑实现匹配的最少次数

  • 状态转移方程：

    f(i,j)=\min\{f(i-1,j)+1,f(i,j-1)+1,f(i-1,j-1)+\delta(A_i\ne B_j)\}

  • 边界与答案：

    f(0, i)=i, f(j, 0)=j;\ f(l_A, l_B)

  • 时间复杂度：​O(l_Al_B)

树与图上的问题

• 快乐聚会：快乐指数 ​a_i，直接上下级不能同时参加，求最大快乐指数和

  • 状态：​f(x, 1/0) 表示员工 ​x 参见/不参加聚会时其与其下属的最大快乐指数之和

  • 状态转移方程：

    f(x,1)=\sum_{y\in S(x)}{f(y,0)}+a_x \\ f(x,0)=\sum_{y\in S(x)}\max\{f(y,0),f(y,1)\}

  • 边界与答案：

    f(leaf, 1)=a_{leaf}, f(leaf,0)=0;\ \max\{f(root, 0),f(root,1)\}

  • 时间复杂度：​O(n)

其他类型的问题

• 概率与期望问题
• 背包问题
• 轮廓线问题
• 组合与计数问题
• 数论、字符串、计算几何中的问题
• · · ·

状态空间中的算法

• 动态规划
• 分治：子问题互不重叠，最优子结构需考虑全部子问题
• 贪心：子问题互不重叠，最优子结构仅考虑极少子问题

分治与贪心

经典算法

• 归并排序：分治
• 逆序对个数：分治
• 快速排序：分治
• 第 ​k 大数：贪心
• 矩阵快速幂：贪心

复数乘法优化

• 四次乘法两次加法 ​\rightarrow 三次乘法五次加法

主定理

• 若 ​d\gt \log_ba,\ T(n)=O(n^d)
• 若 ​d=\log_ba,\ T(n)=O(n^d\log n)
• 若 ​d\lt \log_ba,\ T(n)=O(n^{\log_ba})

分治

一维数值积分

求 ​\int_a^bf(x)dx

• 插值：拉格朗日插值多项式
  A(x)=\sum_{i=0}^{n-1}f(x_i)\prod_{j\ne i}\frac{(x-x_j)}{(x_i-x_j)}
• 梯形法为一次插值，精度不够
• 二次插值：取 ​a,\ b,\ m=\frac{a+b}{2}
  P(x)=f(a)\frac{(x-m)(x-b)}{(a-m)(a-b)}+f(m)\frac{(x-a)(x-b)}{(m-a)(m-b)}+f(b)\frac{(x-a)(x-m)}{(b-a)(b-m)}
• 辛普森积分法
  \int_a^bf(x)dx\approx\int_a^bP(x)dx=\frac{b-a}{6}\Big(f(a)+4f(\frac{a+b}{2})+f(b)\Big)
• 自适应辛普森积分法：分治过程中，若再划分后优化量小于 ​\epsilon，停止迭代

多项式乘法

• 系数表示
• 点值表示
• 快速傅里叶变换（Fast Fourier Transform, FFT）
• 快速傅里叶逆变换（IFFT）

贪心

二分查找

• 本质：有序数组查找四个位置：是否等于；上/下界

• 实现细节：

  • 转换为左闭右开区间内求单增序列的下界问题
  • 中点选取：​mid=l+\frac{1}{2}(r-l)
  • while 判断：​l\lt r
  • 状态转移：​l=mid+1 或 ​r=mid
  • a[mid] 转移条件？转移到哪个区间？——判断区间满足性

• 代码：找 ​\gt|\ge v 的最左元

int l = 1, r = n - 1;
while(l < r) {
    int mid = l + (r - l) / 2;
    if (a[mid] >|>= v) r = mid;
    else l = mid + 1;
}
return a[l];

二分答案