1 Weighted Interval Scheduling
- 设计子函数：前 j 个元素的最优解 OPT(j)
- 具体递推关系
- 选第 j 个任务， $OPT(j) = w_j + OPT(j-1)$
- 不选第 j 个任务， $OPT(j) = OPT(j - 1)$
- 取二者的最大值
- 动态规划分为两步
- Sub-optimal: 发现递推关系
- Tabulation: 记录在内存中，自底向上地执行
2 分段最小二乘 (Segmented Least Square)
- 描述
- 对数据做分段的线性拟合
- 要求有最小的均分误差与最少的直线段数
- 是一个多目标规划问题
- 首先考虑两目标是否同质 → 可以转化为只优化一个目标
- 本问题中，两目标是互斥的，需要把两个目标组合起来
- 互斥目标的解决方式
- 线性组合 → 方便设计，但缺乏可解释性
- 带约束的优化 → 先限制某一个目标，在此条件下优化另一个目标
- 定义
- 均方差为 E，线段个数为 L
- OPT(j): 前 j 个点的最小 cost
- e(i, j): i 到 j 之间的最小均方差
- 递推关系：
- 遍历前面所有的 j - 1 个点
- 假设在第 i 个到第 j 个之间新加一条线
- 新加一条线后，得到的 cost 为 e(i, j) + c + OPT(i - 1)
- 因此最小的cost是所有 i 得到的值的最小值
- 即： $OPT(j) = \min_{1 \le i \le j} { e(i, j) + c + OPT(i - 1) }$
- 时间复杂度： $O(n^3)$
- 算最小二乘的过程需要 O(n)！
3 背包问题
- 描述
- 宝藏的重量为 w，价值为 v，口袋的容量为 W
- 目标：获得最大的总价值
- 定义 OPT(i, w)
- 如果第 i 个物体拿不下， $OPT(i, w) = OPT(i - 1, w)$
- 如果第 i 个物体拿得下
- 需要考虑不拿当前物体的情况，因为该情况有可能为最大值
- $OPT(i, w) = \max{ OPT(i - 1, w), v_i + OPT(i - 1, w - w_i) }$
- 时间复杂度：O(nW)
- 伪多项式时间复杂度
- 是一个 NP-Complete 问题
4 RNA 次级结构
- 规则
- 碱基对只能 A - U，C - G 配对
- 拐弯的地方必须超过3个碱基
- 配对不能交叉
- 设计OPT(i, j)
- 观察：如果有一个配对，在配对中间的部分和配对外面的部分应该是独立的
- 如果第 j 个可以和 i～j 之间的第 t 个进行配对，则 $OPT(i, j) = 1 + OPT(i, t - 1) + OPT(t + 1, j)$
- 对所有的 t，取最大值即可
- 考虑边界情况：
- $i \ge j - 4$, $OPT(i, j) = 0$
- 第 j 个没有配对， $OPT(i, j) = OPT(i, j - 1)$
- 设计算法
- 从最小的距离4开始，在对角线的方向上进行遍历
- 该方法可以将 $O(n^4)$ 转化为 $O(n^3)$
5 Hirschberg’s Alignment Algorithm
5.1 字符串相似度
描述
- 对比两个字符串的区别
- 最小化 gap 和 mismatch 的惩罚
递推关系
5.2 Optimal alignment
- O(m + n)空间复杂度，O(mn)时间复杂度
- 太优雅了，直接欣赏PPT吧