第四章：动态规划（Dynamic Programming）

第一部分：动态规划核心知识点

1. 动态规划的基本概念

动态规划是解决多阶段决策过程最优化的一种数学方法。它将一个复杂的多阶段问题转换为一系列相互联系的单阶段子问题，逐个加以解决（填表法），从而避免了大量重复计算。

2. 适用动态规划求解问题的三大性质

• 最优子结构（最基本条件）：原问题的最优解包含其子问题的最优解。
• 无后效性（马尔科夫性）：某阶段状态一旦确定，就不受这个状态以后决策的影响。即当前状态以后的过程只与当前状态有关，与之前的状态无关。
• 有重叠子问题：子问题之间不独立，一个子问题在下一阶段决策中可能被多次用到。这也是动态规划优于分治法和穷举法的核心优势（通过填表保存结果，空间换时间）。

3. 动态规划求解的基本步骤

遇到实际问题时，通常遵循以下四步：

1. 分析最优子结构：分析问题的最优解特征，划分阶段。
2. 建立状态转移方程（递推公式）：递归地定义最优解，确定动态规划数组（dp表）的含义。
3. 计算最优值：通常采用自底向上的填表方式计算，或者采用自顶向下带备忘录的递归方式计算。
4. 构造最优解：根据计算最优值时记录的信息，反向回溯（Traceback）构造出具体的最优解路径。

4. 动态规划与备忘录法的区别

• 相同点：都用表格保存已解决的子问题答案，避免重复计算。
• 不同点：动态规划是自底向上递推；备忘录法是自顶向下递归，控制结构与直接递归相同，但遇到已计算过的子问题直接查表返回。

---

第二部分：经典例题与推导过程精讲

例题 1：爬楼梯问题 / 斐波那契数列

• 问题描述：10级台阶，每次只能走1级或2级，求总走法数。
• 推导过程：到达第 $i$ 级台阶只能从第 $i-1$ 级走1步，或者从第 $i-2$ 级走2步到达。
• 状态转移方程：$F(n) = F(n-1) + F(n-2)$。
• 边界条件：$F(1)=1$, $F(2)=2$。
• 求解：通过一维数组 dp 从 3 循环到 $n$，dp[i] = dp[i-1] + dp[i-2]，时间复杂度 $O(n)$。

例题 2：求解组合数 $C(n,m)$

• 问题描述：求组合数 $C_n^m$，直接用阶乘公式易溢出且低效。
• 推导过程：利用组合数学性质，从 $n$ 个元素选 $m$ 个，等于“不包含第 $n$ 个元素选 $m$ 个”加上“包含第 $n$ 个元素选 $m-1$ 个”。
• 状态转移方程：C[i][j] = C[i-1][j-1] + C[i-1][j]。
• 边界条件：C[i] = 1, C[i][i] = 1。
• 复杂度：时间复杂度由递归的指数级降为动态规划填表的 $O(n^2)$。

例题 3：整数分解问题

• 问题描述：将正整数 $n$ 无序拆分成最大加数不超过 $m$ 的几种方案。
• 推导过程：设 $f(n,m)$ 为方案数。
  • 当 $n<m$ 时，最大加数不可能超过 $n$，等价于 $f(n,n)$。
  • 当 $n=m$ 时，包含 $m$ 的拆分只有 1 种（即 $n$ 本身），不包含 $m$ 的拆分为 $f(n,m-1)$，故 $f(n,m) = f(n, m-1) + 1$。
  • 当 $n>m$ 时，分为包含 $m$（将剩下的 $n-m$ 用最大不超过 $m$ 的数拆分，即 $f(n-m,m)$）和不包含 $m$（用最大不超过 $m-1$ 的数拆分，即 $f(n,m-1)$）。
• 状态转移方程： dp[n][m] = dp[n][m-1] + dp[n-m][m] ($n>m$)
• 过程：课件中详尽推导了 dp 的计算表，最终得到 7 种。

例题 4：最大连续子序列和

• 问题描述：求序列中连续子数组的最大和。
• 状态定义：dp[j] 表示以第 j 个元素结尾的最大连续子序列和。
• 推导过程：如果前面的累加和 dp[j-1] > 0，则加上当前元素有益；如果 dp[j-1] <= 0，则放弃前面的序列，从当前元素重新开始。
• 状态转移方程：dp[j] = max(dp[j-1] + a[j], a[j])。
• 构造最优解：找到 dp 数组中的最大值，其位置设为 maxj。从 maxj 往前找，直到遇到第一个 dp[k] <= 0 的位置，序列即为 k+1 到 maxj。

例题 5：最长递增子序列 (LIS) 与合唱队形

• 最长递增子序列推导：dp[i] 表示以 a[i] 结尾的最长递增序列长度。检视前面的所有元素 a[j] ($j<i$)，如果 a[i] > a[j]，说明可以将 a[i] 接在 a[j] 后面。
  • 状态转移方程：dp[i] = max(dp[i], dp[j] + 1)，前提是 $a[i] > a[j]$。
• 合唱队形拓展：目标是找一个同学，其左边身高递增，右边身高递减，且总人数最多。
  • 解法：原问题转化为求最长递增序列长度 (f1) 和最长递减序列长度 (f2)。第一遍从左向右求 f1[i]，第二遍从右向左求 f2[i]。最终枚举所有人，取 max(f1[i] + f2[i] - 1) 即为最长合唱队形，时间复杂度 $O(n^2)$。

例题 6：最长公共子序列 (LCS)与最长公共子串

• LCS 问题描述：求两个字符串 A 和 B 的最长不连续公共子序列。
• 状态定义：dp[i][j] 为子序列 $A[0..i-1]$ 和 $B[0..j-1]$ 的最长公共子序列长度。
• 推导过程：
  • 若末尾字符相同（$A[i-1] == B[j-1]$），那么 LCS 长度必定等于它俩去掉末尾字符的 LCS 长度加 1。
  • 若不同，LCS 只能来自于 $A$ 去掉末尾字符与 $B$ 的比较，或者 $A$ 与 $B$ 去掉末尾字符的比较，取二者最大值。
• 状态转移方程：
  • dp[i][j] = dp[i-1][j-1] + 1 ($A[i-1] == B[j-1]$)
  • dp[i][j] = max(dp[i][j-1], dp[i-1][j]) ($A[i-1] \neq B[j-1]$)
• 构造最优解（回溯）：从 dp[m][n] 倒推。如果 dp[i][j] == dp[i-1][j] 则向上走（i--）；如果 dp[i][j] == dp[i][j-1] 则向左走（j--）；如果都不相等，说明该字符在 LCS 中，记录该字符并斜向左上走（i--, j--）。
• 变体：最长公共子串：子串要求必须连续。
  • 状态转移方程：若 $A[i-1] == B[j-1]$，则 dp[i][j] = dp[i-1][j-1] + 1；否则 dp[i][j] = 0（一旦断开，连续长度归零）。遍历时记录最大的 dp 值即可。

例题 7：编辑距离 (Edit Distance)

• 问题描述：将字符串 A 转换为 B 的最少操作次数（插入、删除、替换）。
• 状态定义：dp[i][j] 为将 $A[0..i-1]$ 转换为 $B[0..j-1]$ 的最少操作次数。
• 推导过程：
  • 若当前字符相同：无需操作，代价同前缀，dp[i][j] = dp[i-1][j-1]。
  • 若字符不同，考虑三种操作的最小值：
    • 替换：代价为 dp[i-1][j-1] + 1。
    • 插入：相当于 A 不变，B 少了一个字符（因为插入的字符与 B 匹配了），代价为 dp[i][j-1] + 1。
    • 删除：相当于 A 少了一个字符，B 不变，代价为 dp[i-1][j] + 1。
• 状态转移方程：dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1。
• 边界条件：dp[i] = i（全部删除），dp[j] = j（全部插入）。复杂度 $O(mn)$。

例题 8：矩阵连乘问题

• 问题描述：给定 $n$ 个矩阵，通过加括号确定乘法次序，使总数乘次数最少。
• 状态定义：m[i][j] ($1 \le i \le j \le n$) 为计算矩阵链 $A_i...A_j$ 的最少数乘次数。
• 推导过程：设在第 $k$ 处断开（$i \le k < j$）。总计算量 = 前半段 $A[i:k]$ 的代价 + 后半段 $A[k+1:j]$ 的代价 + 两段结果矩阵相乘的代价（$p_{i-1} \times p_k \times p_j$）。
• 状态转移方程： $m[i][j] = \min_{i \le k < j} \{m[i][k] + m[k+1][j] + p_{i-1} \times p_k \times p_j\}$
• 求解顺序：因为依赖更短的矩阵链，需按矩阵链的长度 (r) 自底向上计算。例如先算所有长度为 2 的，再算长度为 3 的... 三重循环，时间复杂度 $O(n^3)$。
• 构造最优解：使用辅助数组 s[i][j] 记录取得最小值的断点 $k$。通过递归 traceback(s, i, s[i][j]) 和 traceback(s, s[i][j]+1, j) 打印括号。

例题 9：0/1 背包问题

• 问题描述：$n$ 个物品（重量 $w_i$，价值 $v_i$），背包容量 $W$，每个物品选或不选，求最大价值。
• 状态定义：dp[i][r] 表示已考虑前 $i$ 个物品，背包剩余容量为 $r$ 时的最大价值。
• 推导过程：
  • 如果 $r < w_i$，物品放不下，只能不选：dp[i][r] = dp[i-1][r]。
  • 如果 $r \ge w_i$，取“不选”和“选”的最大值：“选”意味着腾出 $w_i$ 的空间，价值增加 $v_i$：dp[i][r] = max(dp[i-1][r], dp[i-1][r-w_i] + v_i)。
• 构造解过程：从 dp[n][W] 开始倒推。如果 dp[i][r] != dp[i-1][r]，说明物品 $i$ 被选中了，将 $r$ 减去 $w_i$，继续向上看 i-1 层。

例题 10：完全背包问题

• 问题描述：与 0/1 背包的区别在于，每种物品可以无限次重复选取。
• 状态转移方程： 基本思路是枚举选 $k$ 个：dp[i][j] = max{dp[i-1][j - k*w[i]] + k*v[i]}。 算法改进：由于选 $k$ 个的情况已经在当前层 dp[i][j-w[i]] 中计算过了，因此可以去掉 $k$ 的循环，直接优化为： dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i]) （注意第二项是 dp[i] 而不是 dp[i-1]）。 时间复杂度从 $O(nC^2)$ 降为 $O(nC)$。

例题 11：资源分配问题

• 问题描述：将一定数量的资源（如 5 名员工）分配给若干使用者（如 3 个商店），使得总收益最大。
• 状态转移方程：dp[i][j] = max(dp[i-1][j-k] + v[i][k]) （其中 $0 \le k \le j$，$k$ 表示分给当前第 $i$ 个商店的资源数量，$v[i][k]$ 是对应的收益表）。同时用 pnum[i][j] 记录取得最大值时的 $k$ 供回溯使用。

例题 12：长江一日游——游艇租赁问题（拓展）

• 问题描述：$n$ 个游艇出租站，从站点 $i$ 到 $j$ 租金为 $r(i,j)$，求从 1 到 $n$ 最少租金。
• 状态转移方程：m[i][j] = min_{i<k<j} \{m[i][k] + m[k][j], r[i][j]\}。即直接到达，或者在中间某个站点 $k$ 停靠的最小值。