动态规划：从基础到实战的深度解析与应用

核心逻辑与数学原理

动态规划（Dynamic Programming, DP）并不是某种具体的代码模板，而是对状态空间进行拓扑排序并剪枝的数学思想。其本质在于将一个复杂问题分解为若干相互重叠的子问题，通过保存子问题的解来避免重复计算，最终导向全局最优解。

DP 的可行性由三个硬性数学指标决定：

最优子结构 (Optimal Substructure)：全局问题的最优解包含子问题的最优解。若定义状态 $S$，其最优值 $V(S)$ 必须能由其子状态集合 $\{S'\}$ 的最优值 $V(S')$ 经由某种单调算子（如 $\min, \max, +$）组合而成。
无后效性 (No-aftereffect)：这是 DP 成立的关键。当前状态确定后，其后的所有状态演变仅取决于当前的状态值，而与到达该状态的路径（即历史决策）无关。用图论语言定义：状态空间必须能被映射为一个有向无环图（DAG），状态为顶点，决策为有向边。
状态重叠 (Overlapping Subproblems)：不同的决策路径会到达相同的子状态。若子问题空间是指数级的，但去重后的实际状态空间是多项式级的，则通过缓存子问题解（解空间去重）可将时间复杂度从 $O(2^N)$ 或 $O(N!)$ 强行压制到 $O(|V| + |E|)$。

状态设计与算法推导

以经典的线性递推问题为例。设计 DP 必须完成三步硬核推导：

1. 状态空间定义

设 $f[i]$ 表示消除了前 $i$ 个决策维度的局部最优解。状态的每个维度必须精确对应边界限制，且必须完全隐去导致该状态的历史路径。

2. 状态转移方程（数学映射）

状态转移实质上是 DAG 上的边权松弛操作。对于目标状态 $i$，其前驱状态集合为 $prev(i)$，转移代价为 $w(j, i)$，则状态转移方程为：

$$f[i] = \max_{j \in prev(i)} \{ f[j] + w(j, i) \}$$

3. 边界条件与拓扑序

必须明确定义没有任何前驱的基准状态（Base Case），通常为 $f[0]$ 或 $f[1]$ 的初始赋值。整个状态空间的计算必须严格按照 DAG 的拓扑序进行，确保在计算 $f[i]$ 时，所有 $j \in prev(i)$ 的 $f[j]$ 已经固化。

C++ 标准源码（NOIP风格）

以下为最长上升子序列（LIS）的 $O(N^2)$ 核心实现，严格遵循 NOIP 考场 Linux 环境编译标准。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 5005;
int a[MAXN];
int f[MAXN];

int main() {
    // 优化标准输入输出流，切断与 stdin/stdout 的同步，加速 I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = 1; // 边界条件：自身独立成一队，长度至少为 1
        for (int j = 1; j < i; ++j) {
            if (a[j] < a[i]) {
                f[i] = max(f[i], f[j] + 1); // 状态转移：从满足无后效性条件的前驱状态转移而来
            }
        }
        ans = max(ans, f[i]); // 维护全局最优解
    }

    cout << ans << "\n";

    return 0;
}

NOIP 实战避坑指南

1. 状态数组未初始化或边界越界

现象：DP 数组未显式初始化，直接读取导致随机脏数据参与 $max/min$ 运算；或者状态计算中出现 $f[i-1]$ 导致 $i=0$ 时数组下标越界。
规避手段：考场上必须明确前驱状态。若求最小价值，数组必须全部 memset 填入 0x3f，且显式将合法起点（如 $f[0]=0$）赋值。涉及 $i-1$ 的循环一律从 1 开始索引。

2. 后效性污染

现象：在计算 $f[i]$ 时，使用了同阶段内已经被修改过的、本不该使用的状态值。常见于背包问题中一维滚动数组的循环方向错误。
规避手段：若当前状态 $f[i][j]$ 依赖于上一阶段的 $f[i-1][j-v]$，而你选择压掉第一维，必须严格倒序枚举 $j$，阻止当前阶段更新后的数据污染尚未更新的后序状态。

经典 NOIP/洛谷真题

1. 洛谷 P1048 [NOIP2005 普及组] 采药

题意描述：给定一个背包容量 $T$ 和 $M$ 件物品，每件物品有采摘时间 $t_i$ 和价值 $v_i$，求在总时间不超过 $T$ 的情况下能获得的最大总价值。
问题本质与解题思路：经典 01 背包问题。每一件物品是一次决策，状态空间受限于剩余时间和已决策物品数。
状态设计：$f[j]$ 表示当前总耗时恰好或不超过 $j$ 时的最大价值。
核心思路：外层遍历物品 $i$，内层倒序遍历时间 $j$ 从 $T$ 递减至 $t_i$。转移方程为：$f[j] = \max(f[j], f[j - t_i] + v_i)$。倒序确保了 $f[j - t_i]$ 依然保存的是未放入物品 $i$ 时的历史最优解，完美符合无后效性。

2. 洛谷 P1091 [NOIP2004 提高组] 合唱队形

题意描述：$N$ 位同学站成一排，求最少需要几位同学出列，使得剩下的同学排成形如 $t_1 < t_2 < \dots < t_k > t_{k+1} > \dots > t_N$ 的山峰形队列。
问题本质与解题思路：双向最长上升子序列（LIS）问题。整个序列由一个转折点 $k$ 划分为左侧的正向 LIS 和右侧的逆向 LIS。
状态设计：$g[i]$ 表示以 $s_i$ 结尾的正向 LIS 长度；$h[i]$ 表示以 $s_i$ 开头的逆向 LIS 长度。
核心思路：通过 $O(N^2)$ 的递推，分别从左向右、从右向左刷出 $g$ 和 $h$ 数组。枚举转折点 $i$，则以 $i$ 为峰顶的最大保留人数为 $g[i] + h[i] - 1$。最终答案即为 $N - \max_{1 \le i \le N} \{g[i] + h[i] - 1\}$。使用 DP 代替暴力枚举排除了子问题重叠的冗余复杂度。