📖 第 6.3 章 ⏱️ 约 55 分钟 🎯 进阶

第 6.3 章：进阶 DP 模式

📝 前置条件： 必须完成第 6.1 章（DP 入门）和第 6.2 章（经典 DP 问题）。进阶模式建立在记忆化、递推和经典 DP 问题（LIS、背包、网格路径）之上。

本章涵盖 USACO Silver 及以上出现的 DP 技术：状压 DP、区间 DP、树形 DP 和数位 DP。每种都有特征性结构，一旦识别出来，问题就变得容易处理。

6.3.1 状压 DP

使用场景： 涉及小集合（N ≤ 20）的子集问题，状态包含「已选了哪些元素」。

核心思路： 用位掩码（整数）表示已选元素的集合。第 i 位为 1 表示元素 i 已选入。

{0, 2, 3} 在 5 个元素的集合中 → 位掩码 = 0b01101 = 13
第 0 位 = 1（元素 0 ∈ 集合）
第 1 位 = 0（元素 1 ∉ 集合）
第 2 位 = 1（元素 2 ∈ 集合）
第 3 位 = 1（元素 3 ∈ 集合）
第 4 位 = 0（元素 4 ∉ 集合）

基本位操作

📄 查看代码：基本位操作

int mask = 0;
mask |= (1 << i);      // 将元素 i 加入集合
mask &= ~(1 << i);     // 从集合中移除元素 i
bool has_i = (mask >> i) & 1;  // 检查元素 i 是否在集合中

// 枚举 mask 的所有子集
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // 处理子集 'sub'
}
// 若需要包含空集，在循环后再处理 sub=0

// 统计置位数（集合中的元素数）
int count = __builtin_popcount(mask);   // int 类型
int count = __builtin_popcountll(mask); // long long 类型

经典题：旅行商问题（TSP）— O(2^N × N²)

题目： N 座城市，完全加权图，找访问每座城市恰好一次的最小代价哈密顿路径。

状态： dp[mask][u] = 恰好访问了 mask 中城市、当前在城市 u 时的最小代价。

Bitmask DP State Space

转移： 扩展到 mask 中没有的城市 v：

dp[mask | (1<<v)][v] = min(dp[mask|(1<<v)][v], dp[mask][u] + dist[u][v])

📄 C++ 完整代码

// TSP 状压 DP — O(2^N × N²)
// N ≤ 20 时可用（2^20×400 ≈ 4×10^8，较紧；N≤18 更安全）
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = 1e18;

int n;
int dist[20][20];
ll dp[1 << 20][20];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> dist[i][j];

    // 初始化：全部为 INF
    for (int mask = 0; mask < (1 << n); mask++)
        fill(dp[mask], dp[mask] + n, INF);

    // 初始条件：从城市 0 出发，只访问了城市 0
    dp[1][0] = 0;  // mask=1（第 0 位置 1），在城市 0，代价=0

    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u))) continue;  // u 不在当前集合中
            if (dp[mask][u] == INF) continue;

            // 尝试扩展到尚未访问的城市 v
            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;  // v 已访问
                int newMask = mask | (1 << v);
                dp[newMask][v] = min(dp[newMask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }

    int fullMask = (1 << n) - 1;  // 所有城市都已访问
    ll ans = INF;
    for (int u = 1; u < n; u++) {
        ans = min(ans, dp[fullMask][u] + dist[u][0]);  // 返回城市 0 形成环
    }

    cout << ans << "\n";
    return 0;
}

⚠️ 内存警告： dp[1<<20][20] 使用约 168MB。N=20 时接近典型 256MB 内存限制。若距离用 int 而非 long long，内存减半约 84MB。

6.3.2 区间 DP

使用场景： 较大区间的答案可以由较小区间的答案构建。关键词：「合并」「分割」「爆破」「矩阵链」。

核心结构：

dp[l][r] = 区间 [l, r] 上子问题的最优答案
初始条件：dp[i][i] = 平凡值（单个元素）
转移：dp[l][r] = 对 k ∈ [l, r-1] 的 min/max：
        dp[l][k] + dp[k+1][r] + cost(l, k, r)
填充顺序：按区间长度递增（len = r - l + 1）

经典题：矩阵链乘法 — O(N³)

题目： N 个矩阵依次相乘，矩阵 i 维度为 dims[i] × dims[i+1]，找最小化标量乘法次数的括号化方案。

状态： dp[l][r] = 计算矩阵 l 到 r 乘积的最少乘法次数。

Interval DP Fill Order

📄 ![Interval DP Fill Order](../images/interval_dp_fill_order.svg)

// 矩阵链乘法 — O(N³)，O(N²) 空间
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = 1e18;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> dims(n + 1);
    for (int i = 0; i <= n; i++) cin >> dims[i];

    vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, 0));

    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            dp[l][r] = INF;

            for (int k = l; k < r; k++) {
                ll cost = dp[l][k] + dp[k+1][r]
                        + (ll)dims[l-1] * dims[k] * dims[r];
                dp[l][r] = min(dp[l][r], cost);
            }
        }
    }

    cout << dp[1][n] << "\n";
    return 0;
}

工作示例： 3 个矩阵 A(10×30)，B(30×5)，C(5×60)

dp[1][2] = 10×30×5 = 1500
dp[2][3] = 30×5×60 = 9000
dp[1][3]：k=2 → dp[1][2] + dp[3][3] + 10×5×60 = 1500+0+3000 = 4500 ← 最小！
答案：4500（括号化为 (A×B)×C）

经典题：气球爆破

📄 查看代码：经典题：气球爆破

// dp[l][r] = 只爆破 (l, r) 中所有气球的最大金币
// 关键洞察：考虑 [l, r] 中**最后**爆破的气球 k
vector<int> val(n + 2);
val[0] = val[n + 1] = 1;
for (int i = 1; i <= n; i++) cin >> val[i];

vector<vector<ll>> dp(n + 2, vector<ll>(n + 2, 0));

for (int len = 1; len <= n; len++) {
    for (int l = 1; l + len - 1 <= n; l++) {
        int r = l + len - 1;
        for (int k = l; k <= r; k++) {
            // k 是 [l, r] 中最后爆破的气球
            ll cost = dp[l][k-1] + dp[k+1][r]
                    + (ll)val[l-1] * val[k] * val[r+1];
            dp[l][r] = max(dp[l][r], cost);
        }
    }
}
cout << dp[1][n] << "\n";

6.3.3 树形 DP

使用场景： 在树上做 DP，节点的状态依赖其子树（后序）或其祖先（前序）。

模式：子树 DP（后序）

树形 DP 总是自底向上运行——叶节点是基础情况，每个内部节点汇总其子节点的结果：

Tree DP Bottom-Up Flow

经典题：树上最大独立集

题目： N 个节点，各有价值 val[u]，选一个子集 S 最大化总价值，约束：若 u ∈ S，则 u 的子节点都不在 S 中。

状态： dp[u][0] = u 不选时 u 子树的最大价值；dp[u][1] = u 选时 u 子树的最大价值。

📄 C++ 完整代码

// 树上最大独立集 — O(N)
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
vector<int> children[MAXN];
int val[MAXN];
long long dp[MAXN][2];

// DFS 后序：先计算所有子节点的 dp，再计算 dp[u]
void dfs(int u) {
    dp[u][1] = val[u];  // 选 u：得到 val[u]
    dp[u][0] = 0;        // 不选 u：这个节点得 0

    for (int v : children[u]) {
        dfs(v);  // ← 先处理子节点（后序）

        // 若选 u：子节点必须不选
        dp[u][1] += dp[v][0];

        // 若不选 u：子节点可以选也可以不选
        dp[u][0] += max(dp[v][0], dp[v][1]);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, root;
    cin >> n >> root;
    for (int i = 1; i <= n; i++) cin >> val[i];

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        children[u].push_back(v);
    }

    dfs(root);
    cout << max(dp[root][0], dp[root][1]) << "\n";
    return 0;
}

树的直径（两次 DFS）

📄 查看代码：树的直径（两次 DFS）

// 树的直径：任意两个节点间的最长路径
// 两次 DFS 法
// 1. 从任意节点 u 做 DFS → 找最远节点 v
// 2. 从 v 做 DFS → 找最远节点 w
// dist(v, w) = 直径

int farthest_node, max_dist;

void dfs_diameter(int u, int parent, int d, vector<int> adj[]) {
    if (d > max_dist) {
        max_dist = d;
        farthest_node = u;
    }
    for (int v : adj[u]) {
        if (v != parent) dfs_diameter(v, u, d + 1, adj);
    }
}

int tree_diameter(int n, vector<int> adj[]) {
    max_dist = 0; farthest_node = 1;
    dfs_diameter(1, -1, 0, adj);

    int v = farthest_node;
    max_dist = 0;
    dfs_diameter(v, -1, 0, adj);

    return max_dist;
}

6.3.4 数位 DP

使用场景： 统计 [1, N] 范围内满足某个与数字有关的性质的数。

核心思路： 从左到右逐位构建数字，维护「tight」约束（是否仍受 N 的各位限制）。

状态： dp[位置][tight][...其他状态...]

位置：当前决策的是哪一位（0 = 最左位）
tight：是否仍受 N 约束（1 = 是，不能超过 N 对应的位；0 = 否，可以自由使用 0-9）
其他状态：追踪的任何性质（各位之和、零的个数等）

经典题：统计 [1, N] 中各位数字之和能被 K 整除的数

📄 查看代码：经典题：统计 [1, N] 中各位数字之和能被 K 整除的数

// 数位 DP — O(|digits| × 10 × K) 时间，O(|digits| × K) 空间
#include <bits/stdc++.h>
using namespace std;

string num;
int K;
map<tuple<int,int,int>, long long> memo;

// pos：当前数位位置（0-indexed）
// tight：是否受 num[pos] 约束
// rem：当前各位之和 mod K
long long solve(int pos, bool tight, int rem) {
    if (pos == (int)num.size()) {
        return rem == 0 ? 1 : 0;  // 完整数字：有效当且仅当各位之和 ≡ 0（mod K）
    }

    auto key = make_tuple(pos, tight, rem);
    if (memo.count(key)) return memo[key];

    int limit = tight ? (num[pos] - '0') : 9;  // 这一位最大能放的数字
    long long result = 0;

    for (int d = 0; d <= limit; d++) {
        bool new_tight = tight && (d == limit);
        result += solve(pos + 1, new_tight, (rem + d) % K);
    }

    return memo[key] = result;
}

// 统计 [1, N] 中各位之和能被 K 整除的数
long long count_up_to(long long N) {
    num = to_string(N);
    memo.clear();
    long long ans = solve(0, true, 0);
    // 减 1 是因为 0 本身的各位之和为 0（能被 K 整除）
    // 但我们要统计 [1, N]，不是 [0, N]
    return ans - 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long L, R;
    cin >> L >> R >> K;

    cout << count_up_to(R) - count_up_to(L - 1) << "\n";
    return 0;
}

💡 核心思路： tight 标志至关重要。tight=true 时，这一位只能使用 ≤ num[pos] 的数字。一旦放了比 num[pos] 小的数字，后面所有位都自由了（tight 变为 false）。这种「剥离」上界的方式是数位 DP 正确的关键。

本章总结

📌 模式识别指南

模式	题目中的线索	状态	转移
状压 DP	「子集」，N ≤ 20，分配任务	`dp[mask][last]`	翻转位，尝试下一个元素
区间 DP	「合并」「分割」「加括号」	`dp[l][r]`	在 k 处分割，组合
树形 DP	「树」，子树性质	`dp[节点][状态]`	从子节点汇总
数位 DP	「统计具有某性质的数」	`dp[位置][tight][...]`	尝试每个数字 d

🧩 核心框架速查

📄 查看代码：🧩 核心框架速查

// 状压 DP 框架
for (int mask = 0; mask < (1<<n); mask++)
    for (int u = 0; u < n; u++) if (mask & (1<<u))
        for (int v = 0; v < n; v++) if (!(mask & (1<<v)))
            dp[mask|(1<<v)][v] = min(dp[mask|(1<<v)][v], dp[mask][u] + cost[u][v]);

// 区间 DP 框架
for (int len = 2; len <= n; len++)           // 枚举区间长度
    for (int l = 1; l+len-1 <= n; l++) {     // 枚举左端点
        int r = l + len - 1;
        for (int k = l; k < r; k++)           // 枚举分割点
            dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + cost(l,k,r));
    }

// 树形 DP 框架（后序遍历）
void dfs(int u, int parent) {
    for (int v : adj[u]) if (v != parent) {
        dfs(v, u);
        dp[u] = update(dp[u], dp[v]);  // 用子节点信息更新当前节点
    }
}

// 数位 DP 框架
long long solve(int pos, bool tight, int state) {
    if (pos == len) return (state == target) ? 1 : 0;
    if (memo[pos][tight][state] != -1) return memo[pos][tight][state];
    int lim = tight ? (num[pos]-'0') : 9;
    long long res = 0;
    for (int d = 0; d <= lim; d++)
        res += solve(pos+1, tight && (d==lim), next_state(state, d));
    return memo[pos][tight][state] = res;
}

❓ 常见问题

Q1：区间 DP 为什么必须先按长度枚举？

A：因为 dp[l][r] 依赖 dp[l][k] 和 dp[k+1][r]，两者的长度都小于 r-l+1。所以所有更短的区间必须在 dp[l][r] 之前计算。按长度从小到大枚举满足这个要求。若直接枚举 l 和 r，可能在依赖还没准备好时就计算 dp[l][r]。

Q2：树形 DP 中，如何处理无根树（给出无向边）？

A：选任意节点为根（通常是节点 1），然后用 DFS 将无向边变为有向边（父 → 子方向）。在 DFS 中传递 parent 参数以避免回到父节点。

void dfs(int u, int par) {
    for (int v : adj[u]) {
        if (v != par) {  // 只访问子节点，不访问父节点
            dfs(v, u);
            // 更新 dp[u]
        }
    }
}

Q3：数位 DP 中 tight=true 和 tight=false 能共用同一个记忆化数组吗？

A：可以，这正是为什么 tight 是状态的一部分。dp[pos][1][rem] 和 dp[pos][0][rem] 是不同的状态，分别记录「有上界约束时的计数」和「自由时的计数」。注意 tight=false 的状态可以在多次调用间复用（一旦 tight 变为 false，后面的位不受约束）。

练习题

题目 6.3.1 — 状压 DP：任务分配 🟡 中等 N 名工人，N 项任务，工人 i 完成任务 j 需要 time[i][j] 小时。将每项任务恰好分配给一名工人，最小化总时间。（N ≤ 15）

提示

`dp[mask]` = 分配了 `mask` 中各任务时的最少总时间。工人下标 = 分配新任务前的 popcount(mask)。

✅ 完整题解

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<vector<int>> t(n, vector<int>(n));
    for (auto& row : t) for (int& x : row) cin >> x;

    vector<long long> dp(1 << n, 1e18);
    dp[0] = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        if (dp[mask] >= (long long)1e18) continue;
        int worker = __builtin_popcount(mask);
        if (worker == n) continue;
        for (int task = 0; task < n; task++) {
            if (mask & (1 << task)) continue;
            dp[mask | (1 << task)] = min(dp[mask | (1 << task)],
                                          dp[mask] + t[worker][task]);
        }
    }
    cout << dp[(1 << n) - 1] << "\n";
}

复杂度： O(2^N × N) 时间和空间，轻松处理 N ≤ 20。

题目 6.3.2 — 区间 DP：回文分割 🟡 中等找将字符串分割成回文子串的最少切割次数。

提示

先用区间 DP 预计算 isPalin[l][r]，再用 cuts[i] = s[0..i] 的最少切割次数。

✅ 完整题解

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s; cin >> s;
    int n = s.size();

    // 第一阶段：回文检查
    vector<vector<bool>> pal(n, vector<bool>(n, false));
    for (int i = n-1; i >= 0; i--)
        for (int j = i; j < n; j++)
            pal[i][j] = (s[i]==s[j]) && (j-i < 2 || pal[i+1][j-1]);

    // 第二阶段：最少切割
    vector<int> cuts(n, n);
    for (int i = 0; i < n; i++) {
        if (pal[0][i]) { cuts[i] = 0; continue; }
        for (int j = 1; j <= i; j++)
            if (pal[j][i]) cuts[i] = min(cuts[i], cuts[j-1] + 1);
    }
    cout << cuts[n-1] << "\n";
}

复杂度： O(N²)。

题目 6.3.3 — 树形 DP：最大匹配 🔴 困难在树上找最大匹配（共享顶点最少的最大边集合）。

提示

dp[u][0] = u 不匹配时 u 子树的最大匹配数；dp[u][1] = u 与某个子节点匹配时 u 子树的最大匹配数。

✅ 完整题解

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int> adj[MAXN];
int dp[MAXN][2];

void dfs(int u, int par) {
    dp[u][0] = dp[u][1] = 0;
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        dp[u][0] += max(dp[v][0], dp[v][1]);
    }
    for (int v : adj[u]) {
        if (v == par) continue;
        int gain = 1 + dp[v][0] - max(dp[v][0], dp[v][1]);
        dp[u][1] = max(dp[u][1], dp[u][0] + gain);
    }
}

int main() {
    int n; cin >> n;
    for (int i = 0; i < n-1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    dfs(1, 0);
    cout << max(dp[1][0], dp[1][1]) << "\n";
}

复杂度： O(N)。

题目 6.3.4 — 数位 DP：统计幸运数 🟡 中等「幸运数」只包含数字 4 和 7，统计 [1, N] 中的幸运数数量。

提示

用 BFS 枚举所有幸运数（4, 7, 44, 47, 74, 77, ...），与 N 比较。

✅ 完整题解

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n; cin >> n;
    int count = 0;
    queue<long long> q;
    q.push(4); q.push(7);
    while (!q.empty()) {
        long long x = q.front(); q.pop();
        if (x > n) continue;
        count++;
        if (x <= n / 10) {
            q.push(x * 10 + 4);
            q.push(x * 10 + 7);
        }
    }
    cout << count << "\n";
}

复杂度： O(2^digits) ≈ O(2^18) 最坏情况。

⚠️ 进阶 DP 常见错误

展开——竞赛前必读

状压 DP 陷阱：

❌ mask >> i & 1 被解析为 mask >> (i & 1)——始终写 (mask >> i) & 1
❌ 枚举子掩码：for (sub=mask; sub>0; sub=(sub-1)&mask) 跳过了 sub=0——若空集有效，手动添加 sub=0
❌ 忘记 __builtin_popcount 统计的是置位数，不是 0..n-1 中的数

区间 DP 陷阱：

❌ 按 (l, r) 顺序而非按区间长度填充——dp[l][k] 可能还没计算好
❌ 分割点范围：k 应该从 l 到 r-1，不是 l 到 r
❌ 初始化错误：dp[i][i] = 0（初始条件），不是 INF

树形 DP 陷阱：

❌ 栈溢出：N > 10^5 时，将递归改为迭代 DFS
❌ 忘记 if (v == parent) continue——在无向边上会无限循环
❌ 换根 DP 中，换根前忘记减去子节点的贡献

数位 DP 陷阱：

❌ tight 标志未传递：若 tight=true，下一位 ≤ N 对应位的数字
❌ 前导零：追踪 started 标志，避免「007」和「7」被重复计数
❌ tight=true 的记忆化条目不能复用——tight=false 的状态可以复用

C++ 竞赛编程：USACO 学习指南