动态规划 | blog of peter

动态规划（Dynamic Programming，DP）是算法世界里最具张力、也最容易让人"卡壳"的一个主题。它的代码往往只有寥寥数行，思想却能在陌生题目面前把人挡在门外；它的理论门槛看似只是一句"分治 + 记忆化"，但能否在第一时间构造出正确的状态定义，几乎直接决定了"会做"与"不会做"。本文将以 DP 的三要素为主线，从最朴素的斐波那契讲起，一路推进到背包家族、区间 DP、树形 DP 与状态压缩，并讨论记忆化与递推的取舍，力图把"为什么这样设计状态"的直觉讲透。

一、为什么需要动态规划：动机与起源

先看一个最朴素的问题：求第 $n$ 个斐波那契数。最容易想到的写法是直接照搬递推式：

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

这段代码在 $n=40$ 时就已经明显感觉到延迟， $n=50$ 几乎无法接受。原因在于它做了海量的重复计算：fib(5) 会调用 fib(4) 与 fib(3)，而 fib(4) 又会再次调用 fib(3) 与 fib(2)，于是 fib(3) 被算了两次，越往下重复越严重，整体时间复杂度退化为 $O(2^n)$ 。

如果我们把每个 fib(k) 的结果第一次算出来时记到一张表里，后续再遇到就直接查表，复杂度立刻降到 $O(n)$ 。这就是动态规划最核心的动机：用空间换时间，消除重叠子问题的重复计算。

但 DP 真正的威力远不止于"加个记忆化"。它是一种建模方式：把一个复杂的最优化或计数问题，分解成若干个规模更小的子问题，并保证子问题的解能够组合出原问题的解。一旦你能写出正确的"状态"和"转移"，剩下的就只是工程实现。

需要强调的是，DP 不是贪心，也不是普通的分治：

贪心要求每一步的局部最优能导向全局最优，这需要问题具有"贪心选择性质"，并非所有问题都满足。
分治把问题切成互不相交的子问题分别求解；DP 则面向重叠的子问题——子问题之间共享更小的子问题，反复求解会浪费。
DP 还额外要求最优子结构：原问题的最优解可以由子问题的最优解构造出来。

理解这三者的边界，是判断一道题该用哪种方法的第一步。

二、核心思想与正确性直觉

动态规划的正确性建筑在两个性质之上，缺一不可。

2.1 最优子结构

如果一个问题的最优解，可以由其子问题的最优解组合而成，就称该问题具有最优子结构。以 0/1 背包为例：在容量为 $W$ 、前 $i$ 个物品中选出一个价值最大的方案，它的最优解要么包含第 $i$ 个物品（那么前 $i-1$ 个物品在容量 $W - w_i$ 中的最优解就是它的子问题），要么不包含（前 $i-1$ 个物品在容量 $W$ 中的最优解就是它的子问题）。两种情况都依赖于"子问题的最优解"，于是最优子结构成立。

反例是"最长简单路径"：从 $u$ 到 $v$ 的最长简单路径并不能由某个中间节点 $k$ 的最长路径拼接而成，因为拼接后可能产生环、违反"简单"约束。这类问题没有最优子结构，通常不能用 DP 直接求解。

2.2 重叠子问题

子问题被反复求解，是 DP 有意义的另一个前提。斐波那契是最典型的例子；LCS 中 dp[i][j] 也会被 dp[i+1][j] 与 dp[i][j+1] 同时依赖。如果一个问题的子问题树是"树形"的（互不重叠），那么用普通分治就够了，不需要 DP。

2.3 无后效性

这是状态设计时最容易踩坑的一条约束：“现在怎么走到这里"不影响"未来能怎么走”，只取决于"现在在哪里"。换句话说，状态必须完整地刻画"从现在起所有可能决策的后果"，过去的细节不能在暗中影响未来。

举个反面例子：求网格图从左上到右下的最短路径，如果用"当前走了哪些格子"作为状态，那状态数会爆炸，而且带有强烈后效性；但如果状态只取"当前坐标 $(i, j)$ "，因为每一步只往右、往下走，过去的路径形状不影响从 $(i, j)$ 出发的最优决策，无后效性成立，DP 就能工作。

无后效性常常是状态设计成败的关键：当你发现某个状态似乎"漏了什么信息"导致转移写不出来，往往就是需要把那个信息补进状态维度里；反之，如果状态维度太多导致爆炸，就要思考能否用某种性质把维度压缩掉。

三、DP 三要素：状态、转移、边界

把任何一道 DP 题拆开，最终都要回答三个问题。

3.1 状态定义

“dp 数组的含义是什么” 是 DP 建模中最关键的一步，往往也是题目的难点。一个好的状态定义应当满足：

完备性：原问题的答案能从某个（或某些）状态推出。
可转移性：每个状态都能由"更小"的状态计算得到，且计算顺序是清晰的（通常构成 DAG）。
无后效性：如上节所述。
规模可控：状态总数在时间、空间预算之内。

状态定义的"维度"直接决定复杂度。一维状态 $O(n)$ 、二维状态 $O(n^2)$ 是最常见的；当问题带额外约束（如"恰好选 $k$ 个"“容量恰好为 $W$ ”）时，往往要把约束升级为状态的一维。

3.2 状态转移方程

转移方程描述"如何从已知状态推出新状态"。它本质上是对"最后一步决策"的枚举：考虑到达当前状态的最后一种选择是什么，枚举所有可能，取最优（最优化问题）或求和（计数问题）。

写转移方程时，一个反复有用的思路是：“我从哪里来” 或 “我到哪里去”。

“我从哪里来”：对于状态 dp[i]，枚举它的前驱 dp[j]（ $j < i$ ），用前驱更新自己。LIS、背包都是这种写法。
“我到哪里去”：对于状态 dp[i]，枚举它能转移到的后继 dp[k]，用自己更新后继。图上 DP 常用。

两种视角等价，选哪种取决于哪种枚举更自然。

3.3 边界条件与初始化

边界条件是 DP 的"地基"。常见的初始化模式有：

空集是合法的：如背包问题中 dp[0][w] = 0（一个物品都不选，价值为 0）。
非法状态设为 $-\infty$ 或 $0$ ：计数问题中，不可达状态贡献为 0；最优化问题中，不可达状态设为 $-\infty$ 防止被错误转移。
起点为 1：如路径计数中 dp[start] = 1。

边界写错是 DP 题最常见的 bug 来源之一。一个有效的检查手段是：对每个转移，确认它引用的所有前驱状态都已被正确初始化，特别是"恰好"“至多”"至少"这类约束下的非法状态。

四、两种实现范式：自顶向下与自底向上

DP 有两种等价的实现方式，理解它们的差异对工程实践很重要。

4.1 自顶向下（记忆化搜索）

从原问题出发，递归地求解子问题，遇到已经算过的子问题直接返回缓存。本质是"带缓存的递归"。

#include <vector>

// 自顶向下：记忆化搜索
int fibMemo(int n, std::vector<int>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

int fib(int n) {
    std::vector<int> memo(n + 1, -1);
    return fibMemo(n, memo);
}

它的优点是只计算真正需要的状态，对状态空间稀疏的问题（如值域很大但实际可达状态少）非常友好；代码结构贴近自然递推式，思考负担小。缺点是递归调用栈有深度限制，常数因子也略大。

4.2 自底向上（递推）

从最小子问题开始，按某种拓扑顺序逐个填表，直到原问题。

int fib(int n) {
    if (n <= 1) return n;
    std::vector<int> dp(n + 1, 0);
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
    return dp[n];
}

自底向上没有递归栈开销，常数小，且天然适合做空间优化（滚动数组）。缺点是必须自己想清楚计算顺序，确保填某个状态时它依赖的状态都已就绪；对稀疏状态空间也会"白白"计算一些用不到的状态。

4.3 如何选择

维度	自顶向下	自底向上
思考方式	贴近递推式，自然	需要规划填表顺序
状态稀疏性	只算需要的状态	可能多算无用状态
空间优化	较难做滚动	容易做滚动
栈深度	受递归深度限制	无栈问题
常数	较大（函数调用）	较小

经验上：先写记忆化搜索保证正确，再视情况改写为递推做优化。在状态依赖关系复杂（如某些图上 DP、数位 DP）时，记忆化搜索的代码量明显更短、更不易错。

五、斐波那契：DP 的最小工作集

回到开篇的斐波那契。把它套进 DP 三要素的框架：

状态：dp[i] 表示第 $i$ 个斐波那契数。
转移：dp[i] = dp[i-1] + dp[i-2]。
边界：dp[0] = 0, dp[1] = 1。

注意一个空间优化的细节：转移只依赖前两项，所以根本不需要整个数组，两个变量就够了：

int fib(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

这种"只保留固定前驱"的优化思路在 DP 中极为常见，后文的背包空间优化也是同一思想。斐波那契本身简单，但它把 DP 的所有要素都浓缩在了一起：状态定义、转移方程、边界、空间优化、两种实现范式。理解了它，就理解了 DP 的骨架。

六、0/1 背包：最优化 DP 的范式

6.1 问题描述

有 $n$ 个物品，第 $i$ 个物品重量为 $w_i$ 、价值为 $v_i$ 。背包容量为 $W$ 。每个物品最多选一次，求能装入背包的物品的最大总价值。

6.2 状态与转移

状态：dp[i][j] 表示前 $i$ 个物品中、总重量不超过 $j$ 时的最大价值。
转移：对第 $i$ $i$ 个物品，分"不选"和"选"两种决策。
- 不选：dp[i][j] = dp[i-1][j]。
- 选（仅当 $w_i \le j$ ）：dp[i][j] = dp[i-1][j-w_i] + v_i。
- 取两者较大值。
边界：dp[0][j] = 0（一个物品都不选，价值为 0）。

这里的关键直觉是：枚举"最后一个决策"——对第 $i$ 个物品的最后一步决策只有两种（选或不选），分别对应两个子问题，取最优。

#include <vector>
#include <algorithm>

// dp[i][w] = 前i个物品，容量为w时的最大价值
int knapsack01(const std::vector<int>& weight,
               const std::vector<int>& value, 
               int capacity) {
    int n = weight.size();
    std::vector<std::vector<int>> dp(n + 1, 
        std::vector<int>(capacity + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            if (weight[i-1] <= w) {
                dp[i][w] = std::max(
                    dp[i-1][w],                          // 不选
                    dp[i-1][w - weight[i-1]] + value[i-1]  // 选
                );
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[n][capacity];
}

复杂度：时间 $O(nW)$ ，空间 $O(nW)$ 。注意 $W$ 是数值大小而非输入规模，所以 0/1 背包是伪多项式时间算法——这正是它能被用于子集和等 NP 问题的近似求解，但也意味着 $W$ 很大时它并不"快"。

6.3 空间优化：滚动数组

观察转移：dp[i][*] 只依赖 dp[i-1][*]，更早的行不再需要。于是可以把第一维压掉，只剩一个长度 $W+1$ 的一维数组。但这里有个陷阱：如果正序遍历 $w$ ，更新 dp[w] 时用到的 dp[w - w_i] 已经是"本层"更新过的值，相当于第 $i$ 个物品被选了多次，退化成完全背包。

正确做法是倒序遍历，保证 dp[w - w_i] 仍然是"上一层"的旧值：

// 空间优化版本
int knapsack01Opt(const std::vector<int>& weight,
                  const std::vector<int>& value, 
                  int capacity) {
    std::vector<int> dp(capacity + 1, 0);
    
    for (size_t i = 0; i < weight.size(); i++) {
        // 倒序遍历，避免重复计算
        for (int w = capacity; w >= weight[i]; w--) {
            dp[w] = std::max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }
    return dp[capacity];
}

复杂度：时间 $O(nW)$ ，空间 $O(W)$ 。这种"倒序保证每物品只用一次、正序允许重复使用"的差别，是理解整个背包家族的钥匙。

6.4 方案回溯

只求最大价值往往不够，常常还要输出具体方案。做法是保留完整二维 dp 表，从 dp[n][W] 倒推：若 dp[i][j] != dp[i-1][j]，说明第 $i$ 个物品被选了，回退到 dp[i-1][j-w_i]；否则没选，回退到 dp[i-1][j]。这样能在 $O(n)$ 时间内还原一种最优方案。

七、背包家族：01、完全、多重

背包问题是 DP 最庞大的一个分支，理解了 0/1 背包，其余变种大多是"调参"。

7.1 完全背包

每个物品可以选无限次。只需把 0/1 背包空间优化版本中的倒序遍历改成正序即可：

#include <vector>
#include <algorithm>

// 完全背包：每件物品可选无限次
int knapsackComplete(const std::vector<int>& weight,
                     const std::vector<int>& value,
                     int capacity) {
    std::vector<int> dp(capacity + 1, 0);
    for (size_t i = 0; i < weight.size(); i++) {
        // 正序遍历：允许同一物品被多次选取
        for (int w = weight[i]; w <= capacity; w++) {
            dp[w] = std::max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }
    return dp[capacity];
}

直觉解释：正序遍历时，dp[w - w_i] 在本层可能已经"用过"第 $i$ 个物品，于是 dp[w] 就能在此基础上再用一次，等价于无限次选取。经典应用是找零钱最少硬币数（把"价值"换成"硬币数"，求最小）、完全背包方案数等。

7.2 多重背包

每个物品有一个数量上限 $c_i$ （既不是 1 也不是无穷）。最朴素的写法是把第 $i$ 个物品拆成 $c_i$ 个独立物品，做 0/1 背包，时间 $O(nW \sum c_i)$ 。当 $c_i$ 较大时这太慢。

二进制分组优化：把 $c_i$ 拆成 $1, 2, 4, \dots, 2^k, r$ （ $r$ 为余数），这样 $O(\log c_i)$ 个"打包物品"就能组合出 $[0, c_i]$ 中的任意数量，整体时间降到 $O(nW \sum \log c_i)$ 。

#include <vector>
#include <algorithm>

// 多重背包：二进制分组优化
int knapsackMultiple(const std::vector<int>& weight,
                     const std::vector<int>& value,
                     const std::vector<int>& count,
                     int capacity) {
    std::vector<int> dp(capacity + 1, 0);
    for (size_t i = 0; i < weight.size(); i++) {
        int remaining = count[i];
        // 把 count[i] 拆成 1,2,4,...,2^k, r
        for (int k = 1; remaining > 0; k <<= 1) {
            int take = std::min(k, remaining);
            remaining -= take;
            int w = weight[i] * take;
            int v = value[i] * take;
            // 当作 0/1 背包处理这一组
            for (int c = capacity; c >= w; c--) {
                dp[c] = std::max(dp[c], dp[c - w] + v);
            }
        }
    }
    return dp[capacity];
}

进一步还有单调队列优化，能把多重背包做到 $O(nW)$ ，思路是把"对每个容量 $c$ ，从 $c - w_i, c - 2w_i, \dots$ 这些位置中取滑动窗口最大值"用单调队列维护。本文不展开，但要记住这是面试与竞赛的常考点。

7.3 分组背包与变种

分组背包：物品分成若干组，每组最多选一个。转移时多一层"组内枚举"。
依赖背包：物品之间有依赖关系（选 $A$ 必须先选 $B$ ），通常转化为树形 DP。
方案数背包：把 max 换成 +=，初始化 dp[0] = 1，用于求"恰好装满"的方案数。

背包家族的核心思想高度统一：状态还是"前 $i$ 个物品 + 容量 $j$ "，区别只在于"第 $i$ 个物品能怎么选"导致的转移形式不同。掌握了 0/1 与完全，其余变种都是组合拳。

八、最长公共子序列（LCS）

8.1 问题描述

给定两个字符串 $A$ 、 $B$ ，求它们的最长公共子序列长度（子序列不要求连续）。

8.2 状态与转移

状态：dp[i][j] 表示 $A$ 的前 $i$ 个字符与 $B$ 的前 $j$ 个字符的 LCS 长度。
转移：看 $A[i-1]$ $A [i - 1]$ 与 $B[j-1]$ $B [j - 1]$ 是否相等。
- 相等：dp[i][j] = dp[i-1][j-1] + 1（这两个字符配对，加到前面的 LCS 上）。
- 不等：dp[i][j] = max(dp[i-1][j], dp[i][j-1])（至少有一个字符不参与配对）。
边界：dp[0][*] = dp[*][0] = 0。

#include <string>
#include <vector>

int longestCommonSubsequence(const std::string& text1, 
                              const std::string& text2) {
    int m = text1.size(), n = text2.size();
    std::vector<std::vector<int>> dp(m + 1, 
        std::vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i-1] == text2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

复杂度 $O(mn)$ ，空间 $O(mn)$ 。空间优化上，由于 dp[i][j] 依赖 dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]，可以滚动到两行 $O(\min(m,n))$ ，但需要额外变量保存左上角的旧值。

8.3 与编辑距离的关系

LCS 的转移是编辑距离的一个特例。编辑距离允许插入、删除、替换三种操作，转移为：

若 A[i]==B[j]: dp[i][j] = dp[i-1][j-1]
否则: dp[i][j] = 1 + min(dp[i-1][j-1],  // 替换
                         dp[i-1][j],    // 删除 A[i]
                         dp[i][j-1])    // 插入 B[j]

把"替换"代价设为无穷大（只允许插入/删除），编辑距离就等于 $|A| + |B| - 2 \cdot LCS$ 。LCS 与编辑距离共享同一族状态定义，理解了其中一个，另一个几乎是免费赠送。

8.4 输出具体 LCS

与背包类似，从 dp[m][n] 回溯：若 A[i-1]==B[j-1] 且 dp[i][j]==dp[i-1][j-1]+1，则该字符属于 LCS，向左上走；否则向较大方向走。

九、最长递增子序列（LIS）

9.1 问题描述

给定序列 $a_1, a_2, \dots, a_n$ ，求其最长的严格递增子序列长度（子序列不要求连续）。

9.2 $O(n^2)$ 解法

状态：dp[i] 表示以 $a_i$ 结尾的 LIS 长度。
转移：dp[i] = max(dp[j] + 1)，其中 $j < i$ 且 $a_j < a_i$ 。
边界：dp[i] = 1（每个元素自身构成长度为 1 的子序列）。

#include <vector>
#include <algorithm>

// O(n^2) 解法
int lengthOfLIS_n2(const std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> dp(n, 1);
    int maxLen = 1;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
        maxLen = std::max(maxLen, dp[i]);
    }
    return maxLen;
}

注意状态定义为"以 $a_i$ 结尾"而非"前 $i$ 个元素的 LIS"——前者能保证转移时新元素能合法接在后面，后者则无法在 $O(1)$ 内判断能否拼接。这种"以某处结尾/开头"的技巧在子序列 DP 中极其常见。

9.3 $O(n \log n)$ 解法：耐心排序

$O(n^2)$ 在 $n=10^5$ 时不可接受。一个巧妙的优化是维护一个数组 tails，其中 tails[k] 表示"所有长度为 $k+1$ 的递增子序列中，最小的结尾元素"。tails 始终保持严格递增，于是对新元素 $x$ 可以二分：

若 $x$ 大于 tails 末尾，说明能接在最长子序列后，直接 push_back，LIS 长度 +1。
否则，找到第一个 $\ge x$ 的位置替换之（让同等长度的子序列结尾更小，为未来留出更大接续空间）。

// O(n log n) 解法：二分优化
int lengthOfLIS(const std::vector<int>& nums) {
    std::vector<int> tails;
    
    for (int num : nums) {
        auto it = std::lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    return tails.size();
}

注意：tails 数组并不是一个真实的 LIS，只是其长度等于 LIS 长度。若要还原具体方案，需要在每次二分时记录每个元素对应的"前驱指针"，最后从 tails 末尾对应的元素回溯。

若要求非严格递增（允许相等），把 lower_bound 换成 upper_bound 即可。这种"换一个二分函数"的小调整是 LIS 题目里最常见的陷阱。

9.4 相关问题

LIS 方案数：在 $O(n \log n)$ 解法基础上，对每个 tails[k] 维护一棵平衡树或树状数组，记录"以某值结尾、长度为 $k+1$ 的方案数"。
二维 LIS（俄罗斯套娃信封）：先按一维排序，再对另一维求 LIS。
最长公共递增子序列（LCIS）：LCS 与 LIS 的结合，状态需要三维或巧妙降维。

十、区间 DP

当问题可以描述为"对一个序列/区间做某种合并或划分操作"时，往往用区间 DP。

10.1 通用模板

状态 dp[i][j] 表示处理子区间 $[i, j]$ 的最优解。转移时枚举分割点 $k$ （ $i \le k < j$ ），把区间分成 $[i, k]$ 与 $[k+1, j]$ 两部分：

1	`dp[i][j] = min/max over k of { dp[i][k] + dp[k+1][j] + cost(i,j,k) }`

其中 cost 是合并两部分的代价。计算顺序按区间长度从小到大，保证计算长区间时它包含的所有短区间都已就绪。

#include <vector>
#include <algorithm>

// 区间 DP 模板：以"合并石子"为例
// 每次合并相邻两堆，代价为两堆之和，求最小总代价
int mergeStones(const std::vector<int>& stones) {
    int n = stones.size();
    if (n == 0) return 0;
    // 前缀和，便于快速求区间和
    std::vector<int> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + stones[i];

    // dp[i][j] = 合并区间 [i,j] 的最小代价
    std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
    for (int len = 2; len <= n; len++) {           // 枚举区间长度
        for (int i = 0; i + len - 1 < n; i++) {    // 枚举起点
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {           // 枚举分割点
                dp[i][j] = std::min(dp[i][j],
                    dp[i][k] + dp[k+1][j]);
            }
            dp[i][j] += prefix[j+1] - prefix[i];   // 加上本次合并的代价
        }
    }
    return dp[0][n-1];
}

复杂度 $O(n^3)$ 。区间 DP 的标志是"三重循环：长度、起点、分割点"。

10.2 经典应用

石子合并：如上。
矩阵链乘法：求矩阵连乘的最少乘法次数，cost 是两个子区间矩阵维度的乘积。
回文分割：把字符串切成若干回文子串的最少切割数，先预处理回文判断再区间 DP。
戳气球：反向思考——把"最后戳的气球"作为分割点，是区间 DP 的经典反向建模。

区间 DP 的关键直觉是：最终的一次决策（如最后一次合并、最后一个戳的气球）把区间一分为二，两半互不相干地各自最优。这种"最后一次决策"的视角在最优化 DP 中反复出现。

十一、树形 DP

当问题在一棵树上求解时，状态往往以"以节点 $u$ 为根的子树"为单位。

11.1 没有上司的舞会

经典例题：一棵树代表公司层级，每个节点有权值。选若干节点使权值和最大，但父子不能同时选。

状态：dp[u][0/1] 表示以 $u$ 为根的子树中， $u$ 不选/选时的最大权值和。
转移：
- dp[u][1] = w[u] + sum(dp[v][0])（ $u$ 选了，所有子节点都不能选）。
- dp[u][0] = sum(max(dp[v][0], dp[v][1]))（ $u$ 没选，子节点选不选都行，取较大）。
边界：叶子节点 dp[leaf][1] = w[leaf]，dp[leaf][0] = 0。

#include <vector>
#include <algorithm>

// 树形 DP：没有上司的舞会
void dfs(int u, int parent,
         const std::vector<int>& w,
         const std::vector<std::vector<int>>& children,
         std::vector<std::array<int,2>>& dp) {
    dp[u][0] = 0;
    dp[u][1] = w[u];
    for (int v : children[u]) {
        if (v == parent) continue;
        dfs(v, u, w, children, dp);
        dp[u][0] += std::max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

int maxParty(const std::vector<int>& w,
             const std::vector<std::vector<int>>& children) {
    int n = w.size();
    std::vector<std::array<int,2>> dp(n, {0, 0});
    dfs(0, -1, w, children, dp);
    return std::max(dp[0][0], dp[0][1]);
}

11.2 树的直径

求树上距离最远的两点间的路径长度。状态 dist[u] 表示从 $u$ 出发往子树方向走的最长链长度。转移时维护"经过 $u$ 的最长路径"= 前两条最长的子链之和，更新全局答案。这是树形 DP 中"维护前两大值"的典型套路。

11.3 树形背包

把"树"和"背包"结合：在树上选若干节点、满足父子依赖关系、总代价不超过 $W$ 的最大价值。状态 dp[u][j] 表示在 $u$ 的子树中选代价为 $j$ 的最优解，转移时把每个子树当作一个"物品组"做分组背包。复杂度分析上有"树形背包 $O(nW)$ "的著名结论（用 size 合并技巧）。

树形 DP 的共同特征是：后序遍历保证子树先算完，再合并到父节点。状态维度通常带一个"以 $u$ 为根的子树"的隐含维度，外加一两个 0/1 或大小约束。

十二、状态压缩 DP（状压 DP）

当状态中包含"一个集合是否包含某元素"这种二值信息，且集合规模较小（通常 $\le 20$ ）时，可以用一个整数的二进制位表示整个集合，这就是状态压缩 DP。

12.1 旅行商问题（TSP）

给定 $n$ 个城市的完全图与距离矩阵，求从 0 号城市出发、经过所有城市恰好一次、回到起点的最短路径。

状态：dp[S][v] 表示已访问城市集合为 $S$ 、当前位于 $v$ 时的最短路径长度。
转移：dp[S | (1<<u)][u] = min(dp[S][v] + dist[v][u])，其中 $u \notin S$ 。
边界：dp[1<<0][0] = 0（只访问了起点），其余为 $\infty$ 。
答案： $\min_v (dp[(1<<n)-1][v] + dist[v][0])$ 。

#include <vector>
#include <algorithm>

// 状压 DP：旅行商问题
int tsp(const std::vector<std::vector<int>>& dist) {
    int n = dist.size();
    const int INF = 1e9;
    std::vector<std::vector<int>> dp(1 << n, std::vector<int>(n, INF));
    dp[1][0] = 0;  // 从 0 号城市出发

    for (int S = 1; S < (1 << n); S++) {
        for (int v = 0; v < n; v++) {
            if (!(S & (1 << v))) continue;        // v 不在集合 S 中
            if (dp[S][v] == INF) continue;
            for (int u = 0; u < n; u++) {
                if (S & (1 << u)) continue;        // u 已经访问过
                int next = S | (1 << u);
                dp[next][u] = std::min(dp[next][u], dp[S][v] + dist[v][u]);
            }
        }
    }
    // 回到起点
    int ans = INF;
    for (int v = 0; v < n; v++) {
        ans = std::min(ans, dp[(1 << n) - 1][v] + dist[v][0]);
    }
    return ans;
}

复杂度 $O(2^n \cdot n^2)$ 。这看起来可怕，但对 $n \le 20$ 完全可行——这正是状压 DP 的"甜区"：集合规模在 20 左右、需要记录"哪些元素已用"的问题。

12.2 状压的常用技巧

位运算：S | (1<<i) 加入元素、S & ~(1<<i) 删除元素、S & (1<<i) 判断是否包含、__builtin_popcount(S) 数集合大小。
子集枚举：for (int T = S; T; T = (T-1) & S) 枚举 $S$ 的所有非空子集，复杂度 $O(3^n)$ 。
预处理合法性：很多状压题先预处理"哪些状态合法"（如棋盘上哪些摆放不冲突），再 DP 转移。

经典应用：棋盘覆盖（骨牌铺放）、互不攻击的国王/皇后放置、配对问题、状压背包等。当一道题的 $n \le 20$ 且涉及"用没用过"的集合信息，几乎可以条件反射地想到状压。

十三、记忆化与递推的取舍

前面提到两种范式的差异，这里展开讲讲工程实践中的取舍。

优先用记忆化搜索的场景：

状态空间稀疏。例如某些图上 DP 只有部分状态可达，自底向上会算一堆没用的状态。
转移依赖关系复杂、不易确定计算顺序。例如某些带"跳跃"的 DP、数位 DP 中带前导零与上界约束的转移，记忆化写起来更接近自然递推式。
调试期。记忆化代码更短、更不易在"填表顺序"上出错，先用它对拍验证正确性，再改递推优化常数。

优先用自底向上的场景：

需要空间优化（滚动数组、原地覆盖）。记忆化天然带递归栈，难以做滚动。
递归深度过大（如 $n=10^6$ 的线性 DP），递归会爆栈。
对常数敏感（竞赛中卡常）。递推的循环展开、cache 友好性都更好。
状态依赖形成清晰的拓扑序（如区间 DP 按长度递增、DAG 按拓扑序）。

一个常被忽视的点：记忆化搜索的"懒计算"特性使它对状态空间的实际利用更精确。例如数位 DP 中，每一位的"是否贴上界""是否有前导零"四个分支只有少数真正可达，自底向上递推反而要处理所有组合。这也是数位 DP 几乎都用记忆化模板的原因——详见数位 dp 专篇。

数位 dp 是动态规划中一个独立且庞大的子专题，专门处理"在 $[L, R]$ 范围内满足某种数位性质（如不含 4、各位数字之和为 $k$ ）的数的计数"。它的状态设计（当前位、是否贴上界、是否贴下界、是否有前导零）与转移方式自成一派，是面试与竞赛中的高频考点，数位 dp 专篇对其模板与典型例题做了系统讲解。

十四、横向对比

把本文涉及的几类 DP 放在一起对照：

类型	状态维度	典型复杂度	标志特征
线性 DP（LIS/LCS）	1~2 维	$O(n)$ / $O(n^2)$	沿序列/网格推进
背包 DP	物品 + 容量	$O(nW)$ （伪多项式）	容量维是数值
区间 DP	左右端点	$O(n^3)$	枚举分割点，按长度递增
树形 DP	节点 + 0/1 或大小	$O(n)$ / $O(nW)$	后序遍历，子树合并
状压 DP	集合 + 当前位置	$O(2^n \cdot n)$	集合规模 $\le 20$
数位 DP	位 + 4 个标志	与位数 × 状态数	数位逐位决策，贴上界

记忆口诀：线性背包区间树，状压数位分两路。识别题目类型后，状态定义与转移的"模板"就大致确定了，剩下的功夫在边界与剪枝。

十五、实战场景

15.1 竞赛

DP 是算法竞赛的"半壁江山"。Codeforces Div.2 的 C/D 题几乎必有 DP；NOI/ICPC 区域赛里，树形 DP、状压 DP、数位 DP 都是常考类型。一个常见的备赛策略是：先打通"背包 + 区间 + 树形 + 状压"四大模板，再针对数位、概率/期望 DP、插头 DP 等高阶专题逐个突破。

15.2 工程

在工程实践中，DP 的影子比比不及：

生物信息学：序列比对（LCS / 编辑距离的变体）是 BLAST 等工具的核心。
自然语言处理：分词、词性标注的维特比算法本质是 HMM 上的 DP。
运筹优化：资源分配、排程问题常建模为背包或区间 DP。
版本控制：git diff 的最小编辑脚本就是编辑距离 DP 的方案回溯。
强化学习：值迭代、策略迭代都是 DP 思想在马尔可夫决策过程上的体现，"贝尔曼方程"即是 DP 转移方程。

理解了 DP，你会发现它不只是"一种算法"，而是一种把复杂决策问题"分层拆解 + 组合子解"的思维方式，几乎在任何需要"在多步决策中求最优"的领域都会再次相遇。

十六、常见陷阱与边界条件

状态定义模糊：把"前 $i$ 个"与"以 $i$ 结尾"混用。LIS 必须用"以 $i$ 结尾"，否则转移时无法判断能否拼接。写状态定义时务必问自己：“这个状态是否完整描述了影响未来的所有信息？”
初始化遗漏：尤其是"恰好""至少"约束下，非法状态必须设为 $-\infty$ （最优化）或 $0$ （计数），否则会被错误转移污染。一个检查技巧：对每个转移，逐项确认它引用的前驱都已被正确初始化。
填表顺序错误：自底向上时必须保证依赖关系形成 DAG 且按拓扑序填表。区间 DP 按长度递增、树形 DP 后序遍历、背包倒序/正序的选择，都是这一原则的体现。
滚动数组覆盖：压缩维度时，若引用了"本层"还未更新的旧值，需要额外变量暂存（如 LCS 滚动时左上角的旧值）。背包的倒序遍历正是为了避免覆盖。
后效性未消除：当状态似乎"漏了信息"导致转移不封闭，往往是需要补维度。例如"飞行问题"中必须把"当前剩余油量"纳入状态，否则未来决策会受过去路径影响。
整数溢出：计数类 DP 的答案常常指数级增长，要尽早用 long long 甚至高精度。最优化 DP 中代价之和也可能溢出 int。
负数下标 / 越界：状态中带"差值""偏移"时（如将容量为负的子问题平移到非负区间），极易越界。建议给数组多开几个元素、用偏移量统一处理。
混淆"子序列"与"子串"：子串要求连续（状态通常是 dp[i] 表示以 $i$ 结尾的最长 XX 子串），子序列不要求连续（通常 dp[i][j] 双串或 dp[i] 单串 + 枚举前驱）。两者状态设计差异显著。
lower_bound vs upper_bound：LIS 中求严格递增用 lower_bound，非严格递增用 upper_bound。搞反是常见 bug。
状压的范围判断： $n=20$ 时 $2^n \approx 10^6$ 尚可， $n=25$ 时 $2^n \approx 3 \times 10^7$ 就接近上限。盲目状压会 TLE/MLE，要先估算状态规模。

十七、小结

动态规划的核心，是把"在多步决策中求最优/计数"的问题，拆解为状态 + 转移 + 边界三件套。状态定义是建模的灵魂，决定了问题能否被正确刻画；转移方程是对"最后一步决策"的枚举，决定了子问题如何组合；边界条件是地基，错了就全盘皆输。

实现上，自顶向下的记忆化搜索贴近自然思维、适合稀疏状态与调试，自底向上的递推常数小、易做空间优化、适合大规模与卡常场景。两者等价，取舍看问题特征。

从斐波那契到背包、从 LCS 到 LIS、从区间 DP 到树形 DP 再到状压，每一类问题都有相对固定的状态模板，但真正的能力差异在于"看到陌生题能否第一时间想到正确的状态定义"。这种直觉只能靠刷题与归纳积累：每做一道 DP 题，不妨停下来追问一句——"这道题的状态为什么这样设计？换一种定义会怎样？“久而久之，DP 就会从"玄学"变成"反射”。

最后给学习者一张路线图：先吃透本文的线性 DP（LIS/LCS）与背包家族，再练区间 DP 与树形 DP 的模板题，接着挑战状压 DP 与数位 dp，最后进阶到概率/期望 DP、插头 DP 等高阶专题。每一步都要带着"状态为什么这样设计"的追问，而不是机械套模板。DP 的精髓，正在于这种"建模—验证—优化"的反复打磨之中。