动态规划(1)：DP基础

本文为SJTU-AI2615算法课程的知识点复习，主要复习内容为动态规划基础，包括斐波那契数列、DAG最短路径、最长递增子序列、编辑距离、背包问题等。

动态规划

• ​核心思想：
  • 将问题分解为重叠子问题，通过存储子问题解（记忆化）避免重复计算
  • 要求问题具有最优子结构​（全局最优解包含局部最优解）
• ​关键步骤：
  • 定义子问题
  • 合并重复子问题（转化为DAG）
  • 按拓扑序求解子问题

斐波那契数列

递归解法

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

记忆化搜索

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

动态规划

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

DAG 最短路径

问题描述

• 输入：有向无环图（DAG）、起点 $s$、边权函数 $w(e)$
• 输出：$s$ 到所有顶点的最短路径

动态规划思路

• 时间复杂度：$O(|V| + |E|)$

正确性证明

• 数学归纳法

最长递增子序列

问题描述

• 输入：序列 $a_1, a_2, \ldots, a_n$
• 输出：最长递增子序列长度（LIS）的长度，LIS 指 $a_{i_1} < a_{i_2} < \cdots < a_{i_k}$，其中 $i_1 < i_2 < \cdots < i_k$

动态规划思路

• 子问题：LIS[i] 表示以 $a_i$ 结尾的 LIS 长度

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

编辑距离

问题描述

• 输入：字符串 X 和 Y
• 输出：将 X 转换为 Y 的最小操作次数（插入、删除、替换）

问题转化

• 等价问题：找到最好的对齐方式

动态规划思路

• 子问题：ED[i, j] 表示 X[1..i] 和 Y[1..j] 之间的编辑距离

• 状态转移：

$$ED[i][j] = \min \begin{cases} \, ED[i-1][j-1] + \mathbb{I}(x_i \neq y_j) & \text{替换} \\ \, ED[i][j-1] + 1 & \text{插入} \\ \, ED[i-1][j] + 1 & \text{删除} \end{cases}$$

• 时间复杂度：$O(nm)$

背包问题

问题描述

• 输入：$n$ 件物品，第 $i$ 件物品代价 $c_i$，价值 $v_i$，背包容量 $W$
• 输出：选择物品子集，使得总代价不超过 $W$ 且总价值最大

动态规划思路

• 子问题：f[i, w] 表示考虑前 $i$ 件物品，使用 $w$ 容量时的最大价值
• 状态转移：
  $f[i, w] = \max \{ f[i − 1, w], f[i − 1, w − c_i] + v_i \}$

时间复杂度

• $O(nW)$，但并不是多项式
  • 考虑输入规模 $N$：表示输入所需的比特数
  • $N \ge n$，$N \ge \log W$
  • $O(nW) = O(N \times 2^N)$

总结

注：本文中所有图片均来自张宇昊老师的课程PPT。