动态规划：状态设计、转移方程推导与空间优化

动态规划（Dynamic Programming, DP）是解决多阶段决策最优化问题的核心范式。其本质在于利用子问题之间的重叠特性，通过表格记录已经求解的子问题局部解（记忆化/查表），从而避免朴素递归中的指数级冗余计算。

---

一、动态规划设计哲学与两大先决条件

应用动态规划求解优化问题，必须严格满足以下两个基本特征：

1. 最优子结构性质（Optimal Substructure）：
   一个问题的全局最优解必定包含其子问题的最优解。也就是说，大问题的最优决策可以通过一系列子问题的最优决策推导组合而成。
2. 重叠子问题性质（Overlapping Subproblems）：
   在递归自顶向下分解问题时，相同的子问题在不同的决策路径中被反复出现。若采用常规递归，计算量将呈指数爆炸；动态规划通过自底向上填表保存子解，保证每个子问题仅计算一次。

1.1 状态定义的无后效性（Markov Property）

无后效性要求：某个状态一经确定，系统此后的演化只取决于当前状态值，而不依赖于到达该状态的历史路径。
若所设计的状态包含的信息不足以支持无后效转移，必须扩充状态维度。

典型范例：最大连续子段和

• 若将状态定义为“前 $i$ 个数中的全局最大子段和 $F[i]$”，在考虑第 $i+1$ 个数时，无法判断已选出的最优子段是否与第 $i$ 个数直接相连，因而无法决定第 $i+1$ 个数能否向右连续拼合；
• 修正设计：显式定义 $E[i]$ 为“必须以元素 $a_i$ 结尾的最大连续子段和”。该定义完整封装了连续性约束，支持后续状态的无后效转移。

1.2 “考察最后一步决策”的建模思维

构建动态规划转移方程的标准思维抓手为考察最优方案的最后一步决策：

• 在最优解的最后一个动作处，系统存在哪些互斥且完备的候选选择？
• 每种候选选择会将问题转化为哪一个规模更小的子问题？
• 将各分支代价取极值（$\max$ 或 $\min$），即可直接导出状态转移方程。

---

二、0-1 背包问题与一维空间压缩原理

问题描述：有 $n$ 件物品，第 $i$ 件物品重量为 $w_i \ge 0$、价值为 $v_i \ge 0$；背包总承重上限为 $C$。每件物品只能选择装入 0 次或 1 次。求背包能容纳的最大总价值。

2.1 二维状态转移方程

定义 $dp[i][c]$ 为：仅在候选物品集合 $\{1, 2, \dots, i\}$ 中选取，总重量不超过 $c$（$0 \le c \le C$）时的最大总价值。

考察最后一步决策（面对第 $i$ 件物品）：

1. 不装入第 $i$ 件物品：问题规约为前 $i-1$ 件物品在容量 $c$ 下的最优解，收益为 $dp[i-1][c]$；
2. 装入第 $i$ 件物品（前提为 $c \ge w_i$）：背包需预留 $w_i$ 容量，问题规约为前 $i-1$ 件物品在容量 $c - w_i$ 下的最优解，收益为 $dp[i-1][c - w_i] + v_i$。

综合两分支取最大值，导出状态转移方程：

$$dp[i][c] = \begin{cases} dp[i-1][c], & c < w_i, \\ \max\big(dp[i-1][c],\ dp[i-1][c - w_i] + v_i\big), & c \ge w_i. \end{cases}$$

• 边界条件：$dp[0][c] = 0$（无物品可选时价值为 0）；$dp[i][0] = 0$（容量为 0 时装不下正重量物品）。
• 复杂度：状态总数 $n \times (C+1)$，每个状态转移需 $O(1)$ 时间，时间复杂度与空间复杂度均为 $\Theta(nC)$。

2.2 滚动数组一维化与容量逆序循环的数学原理

观察转移方程可知：计算第 $i$ 阶段的 $dp[i][c]$ 时，仅需依赖上一阶段 $i-1$ 的两项：同容量项 $dp[i-1][c]$ 与更小容量项 $dp[i-1][c - w_i]$。因此可将空间压缩为一维数组 dp[c]。

std::vector<int> dp(C + 1, 0);
for (int i = 0; i < n; ++i) {
    for (int c = C; c >= weight[i]; --c) { // 必须严格逆序遍历容量
        dp[c] = std::max(dp[c], dp[c - weight[i]] + value[i]);
    }
}

[!IMPORTANT]
容量逆序循环的数学依据：
在计算更新 dp[c] 时，等号右侧所需的 dp[c - weight[i]] 必须是上一阶段未放入第 $i$ 件物品时的旧值。

• 若采用逆序循环（$c$ 从 $C$ 递减到 $w_i$）：计算较大容量 dp[c] 时，左侧较小容量单元 c - weight[i] 尚未被本轮循环修改，依然保留着阶段 $i-1$ 的纯净历史值，严格保证了每件物品只被选取至多一次；
• 若采用正序循环（$c$ 从 $w_i$ 递增到 $C$）：较小容量单元先被更新，当循环推进到较大容量时，查到的 dp[c - weight[i]] 已经包含了第 $i$ 件物品，导致同一件物品被重复累加多次，算法退化为完全背包（Unbounded Knapsack）。

---

三、最长公共子序列（LCS, Longest Common Subsequence）

问题描述：给定两个序列 $X = \langle x_1, x_2, \ldots, x_m \rangle$ 与 $Y = \langle y_1, y_2, \ldots, y_n \rangle$。求两序列的最长公共子序列长度（子序列字符相对次序保持一致，但不要求物理连续）。

3.1 状态定义与转移方程

定义 $c[i][j]$ 为：前缀子序列 $X[1 \dots i]$ 与 $Y[1 \dots j]$ 的最长公共子序列长度。

考察最后一步决策（比对末尾字符 $x_i$ 与 $y_j$）：

1. 若 $x_i = y_j$：该字符必然可作为 LCS 的最后一个字符。问题归结为两个缩短前缀的 LCS 长度加 1：
   $c[i][j] = c[i-1][j-1] + 1;$
2. 若 $x_i \ne y_j$：两末尾字符不可能同时作为公共子序列的末尾。公共子序列要么不包含 $x_i$（对应 $c[i-1][j]$），要么不包含 $y_j$（对应 $c[i][j-1]$），取二者较大者：
   $c[i][j] = \max\big(c[i-1][j],\ c[i][j-1]\big).$

$$c[i][j] = \begin{cases} 0, & i = 0 \text{ 或 } j = 0, \\ c[i-1][j-1] + 1, & i, j > 0 \text{ 且 } x_i = y_j, \\ \max(c[i-1][j], c[i][j-1]), & i, j > 0 \text{ 且 } x_i \ne y_j. \end{cases}$$

时间复杂度为 $\Theta(mn)$，空间复杂度为 $\Theta(mn)$。若只需输出长度，可通过保留相邻两行将空间优化为 $O(\min(m, n))$。

---

四、最大连续子段和问题（Maximum Subarray）

问题描述：给定整数数组 $a_1, a_2, \ldots, a_n$（元素可正可负），寻找非空连续子数组 $a_i, \dots, a_j$（$1 \le i \le j \le n$），使得元素之和达到最大。

4.1 状态转移与 Kadane 算法

定义 $E[i]$ 为：必须以元素 $a_i$ 结尾的最大连续子段和。

考察最后一步决策：
以 $a_i$ 结尾的最优子段仅有两种构造选择：

1. 独立成段：由于以 $a_{i-1}$ 结尾的前段和为负数，若拼合反而削弱当前总和，故果断舍弃前序，仅由 $a_i$ 单独构成子段；
2. 与前段拼合：以 $a_{i-1}$ 结尾的前段和为正数，将 $a_i$ 追加在后。

$$E[i] = \max\big(a_i,\ E[i-1] + a_i\big),\qquad E[1] = a_1.$$

全局最优解为所有结尾位置的最大值：
$\text{Answer} = \max_{1 \le i \le n} E[i].$

由于 $E[i]$ 仅依赖前驱 $E[i-1]$，只需单个标量变量维护前驱最大值，即可在线性时间 $\Theta(n)$ 和常数辅助空间 $O(1)$ 内完成求解。

---

五、区间动态规划：矩阵连乘积问题

问题描述：给定 $n$ 个矩阵序列 $\langle A_1, A_2, \ldots, A_n \rangle$，矩阵 $A_i$ 的维度为 $p_{i-1} \times p_i$。矩阵乘法满足结合律，不同加括号次序导致标量乘法总次数产生数量级差异。求计算该矩阵连乘积所需的最少标量乘法次数。

5.1 状态设计与区间分割

定义 $m[i][j]$ 为：计算矩阵子链 $A_i A_{i+1} \cdots A_j$ 所需的最少标量乘法次数（$1 \le i \le j \le n$）。

考察最后一步决策：
在最优加括号方案中，必然存在某个最终分割点 $k$（$i \le k < j$），使得最后一次乘法为两个子结果矩阵相乘：$(A_i \cdots A_k) \times (A_{k+1} \cdots A_j)$。

• 左子矩阵维度为 $p_{i-1} \times p_k$；
• 右子矩阵维度为 $p_k \times p_j$；
• 最后一次矩阵乘法的标量代价为 $p_{i-1} p_k p_j$。

$$m[i][j] = \begin{cases} 0, & i = j, \\ \min_{i \le k < j} \big\{ m[i][k] + m[k+1][j] + p_{i-1} p_k p_j \big\}, & i < j. \end{cases}$$

5.2 填表拓扑顺序

计算 $m[i][j]$ 需要用到长度更短的子区间 $m[i][k]$（长度 $k - i + 1$）与 $m[k+1][j]$（长度 $j - k$）。因此，表格求值必须严格按照区间长度 $r = j - i + 1$ 从 2 递增至 $n$ 进行遍历：

for (int r = 2; r <= n; ++r) { // 区间长度
    for (int i = 1; i <= n - r + 1; ++i) {
        int j = i + r - 1;
        m[i][j] = INF;
        for (int k = i; k < j; ++k) {
            long long cost = m[i][k] + m[k + 1][j] + 1LL * p[i - 1] * p[k] * p[j];
            if (cost < m[i][j]) {
                m[i][j] = cost;
                s[i][j] = k; // 记录最优断开点以重构括号方案
            }
        }
    }
}

状态总数为 $O(n^2)$，每个状态枚举分割点耗时 $O(n)$，总时间复杂度为 $\Theta(n^3)$，空间复杂度为 $\Theta(n^2)$。

---

六、最优二叉搜索树（Optimal BST）

问题描述：给定关键字有序集 $S = \{x_1 < x_2 < \dots < x_n\}$，查找成功的概率分别为 $b_1, \dots, b_n$；虚拟键（表示查找落在开区间 $(x_i, x_{i+1})$ 内失败）的概率分别为 $a_0, a_1, \dots, a_n$。要求构造一棵期望查找深度最小的二叉搜索树。

定义 $w(i, j) = \sum_{l=i}^j b_l + \sum_{l=i-1}^j a_l$ 为区间概率权重和；定义 $m[i][j]$ 为子树覆盖关键字 $x_i \dots x_j$ 时的最小期望查找代价。

考察最后一步决策：枚举该子树以哪一个关键字 $x_k$（$i \le k \le j$）作为根节点：

• 左子树覆盖范围为 $x_i \dots x_{k-1}$；
• 右子树覆盖范围为 $x_{k+1} \dots x_j$；
• 由于整棵子树作为子树挂在根节点下，其内部所有节点的深度均增加 1，因此该子树的总期望代价需额外累加该子树内所有节点的概率权重和 $w(i, j)$：

$$m[i][j] = w(i, j) + \min_{i \le k \le j} \big\{ m[i][k-1] + m[k+1][j] \big\},\qquad (m[i][i-1] = a_{i-1}).$$

基础实现时间复杂度为 $O(n^3)$，利用 Knuth 四边形不等式（最优根节点具有单调性 $s[i][j-1] \le s[i][j] \le s[i+1][j]$）可加速至 $O(n^2)$。

---

七、经典实验题建模与转移方程矩阵

经典实验题	核心考查模型	状态严密定义	状态转移方程与设计要点
独立任务调度	双机负载均衡	$F[i][j]$：处理完前 $i$ 个作业、机器 A 累计耗时为 $j$ 时，机器 B 消耗的最小时间	作业 $i$ 分配给 A 则 $F[i-1][j-a_i]$；分配给 B 则 $F[i-1][j] + b_i$。最终答案为 $\min_j \max(j, F[n][j])$
环形石子合并	环形区间 DP	$m[i][j]$：将连续闭区间 $[i, j]$ 内的石子合并为一堆的最优代价	拆环为二倍长度链（$2n-1$）；按区间长度递增递推：$m[i][j] = \min_{i \le k < j}(m[i][k] + m[k+1][j]) + \sum_{l=i}^j w_l$
数字三角形	DAG 路径最值	$dp[i][j]$：从位置 $(i, j)$ 出发到达底层的最大路径和	采用自底向上逆向递推：$dp[i][j] = a[i][j] + \max(dp[i+1][j], dp[i+1][j+1])$，边界无需特判
租用游艇	有向无环图最短路	$dp[i]$：从起点 1 号码头到达站台 $i$ 的最小租金	枚举上一个经停站点 $k$（$1 \le k < i$）：$dp[i] = \min_{1 \le k < i}(dp[k] + r[k][i])$
最小 $m$ 段和	分段极值优化	$dp[i][j]$：前 $i$ 个数恰好分割为 $j$ 段的最大段和极小值	枚举最后一段的起始位置 $k$：$dp[i][j] = \min_{j-1 \le k < i} \max(dp[k][j-1], \sum_{l=k+1}^i a_l)$
最大 $k$ 乘积	数值分段相乘	$dp[i][j]$：前 $i$ 位数字中插入 $j$ 个乘号所能获得的最大乘积	枚举最后一个乘号的位置 $k$：$dp[i][j] = \max_{j \le k < i}(dp[k][j-1] \times \text{num}(k+1, i))$

---

八、动态规划算法答题规范自查清单

1. 状态定义是否严谨：状态必须完全交代每一个下标变量的取值范围和物理含义，不可遗漏边界下标（如 0 的含义）；
2. 转移方程是否闭合：分类讨论是否涵盖了最后一步的所有决策，是否有遗漏的边界分支；
3. 初值与非法状态标记：求最小值时不可达状态是否正确置为 $+\infty$，求最大值时是否置为 $-\infty$；
4. 填表循环方向：转移方程中被引用的依赖项在计算当前项时是否已经求出（拓扑有序性）；一维压缩时容量循环是否满足防重复覆盖的方向约束。