第 10 章动态规划进阶¶

本章介绍树形 DP、换根 DP、状压 DP、数位 DP 进阶、区间 DP 进阶以及 DP 优化技巧。这些是竞赛中的高频考点，掌握它们能让你的 DP 水平提升一个台阶。

10.1 树形 DP¶

树形 DP 是在树结构上进行动态规划。由于树具有天然的递归结构，树形 DP 通常结合 DFS 实现。

基本思路：从叶子节点向根节点递推，每个节点的 DP 值由其子树决定。

graph TD
    A["根节点 u"] --> B["子节点 v1"]
    A --> C["子节点 v2"]
    A --> D["子节点 v3"]
    B --> E["叶子"]
    B --> F["叶子"]
    C --> G["叶子"]
    D --> H["叶子"]

    style A fill:#ffcc00,stroke:#cc9900
    style B fill:#99ccff,stroke:#0066cc
    style C fill:#99ccff,stroke:#0066cc
    style D fill:#99ccff,stroke:#0066cc

信息从叶子向根汇聚（自底向上），这是树形 DP 的典型模式。

10.1.1 没有上司的舞会（洛谷 P1352）¶

问题：公司里有 n 名员工，每个人有一个快乐值 h[i]。员工之间有上下级关系（形成一棵树）。如果某个员工参加舞会，他的直接下级就不能参加。求舞会的快乐值最大是多少。

状态定义：

dp[u][0] = 以 u 为根的子树中，u 不参加 舞会时的最大快乐值
dp[u][1] = 以 u 为根的子树中，u 参加舞会时的最大快乐值

转移方程：

\[dp[u][0] = \sum_{v \in children(u)} \max(dp[v][0], \; dp[v][1])\]

\[dp[u][1] = h[u] + \sum_{v \in children(u)} dp[v][0]\]

graph TD
    U0["dp[u][0]: u 不参加"] --> V0["下属 v 可以参加或不参加"]
    V0 --> W0["取 max(dp[v][0], dp[v][1])"]

    U1["dp[u][1]: u 参加"] --> V1["下属 v 一定不参加"]
    V1 --> W1["取 dp[v][0]"]

    style U0 fill:#90EE90,stroke:#006600
    style U1 fill:#FFB6C1,stroke:#cc0000

图示：

graph TD
    A["1: h=1"] --> B["2: h=2"]
    A --> C["3: h=3"]
    A --> D["4: h=4"]
    B --> E["5: h=5"]
    B --> F["6: h=6"]

树结构：1 是根，2、3、4 是 1 的下属，5、6 是 2 的下属

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 6005;
vector<int> adj[MAXN];  // 邻接表
int h[MAXN];            // 每个人的快乐值
int dp[MAXN][2];        // dp[u][0]=u不参加, dp[u][1]=u参加
bool has_boss[MAXN];    // 判断谁是根节点（没有老板的就是根）

void dfs(int u) {
    dp[u][0] = 0;         // u 不参加，初始快乐值为 0
    dp[u][1] = h[u];      // u 参加，初始快乐值为 h[u]
    for (int v : adj[u]) {
        dfs(v);            // 先递归处理所有子节点
        dp[u][0] += max(dp[v][0], dp[v][1]); // u 不参加，下属可选
        dp[u][1] += dp[v][0];                 // u 参加，下属不能参加
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i < n; i++) {
        int l, k; // l 是下属，k 是上司
        cin >> l >> k;
        adj[k].push_back(l);
        has_boss[l] = true;
    }
    // 找根节点（没有上司的人）
    int root = 1;
    for (int i = 1; i <= n; i++) {
        if (!has_boss[i]) { root = i; break; }
    }
    dfs(root);
    cout << max(dp[root][0], dp[root][1]) << endl;
    return 0;
}

时间复杂度：O(n)
空间复杂度：O(n)

树形 DP 的实现要点

用邻接表存储树（注意边是有向的，从父指向子）
DFS 先递归到叶子，再回溯时进行状态转移
每个节点的状态只计算一次

10.1.2 树的直径（树形 DP 求法）¶

问题：求一棵树中距离最远的两个节点之间的距离。

状态定义：

d1[u] = 以 u 为根的子树中，从 u 出发向下的最长路径
d2[u] = 以 u 为根的子树中，从 u 出发向下的次长路径

答案：所有节点的 d1[u] + d2[u] 的最大值

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;
vector<pair<int,int>> adj[MAXN]; // 邻接表 (邻居, 边权)
int d1[MAXN], d2[MAXN];          // 最长和次长向下路径
int ans = 0;

void dfs(int u, int parent) {
    d1[u] = d2[u] = 0;
    for (auto& [v, w] : adj[u]) {
        if (v == parent) continue;
        dfs(v, u);
        int dist = d1[v] + w; // 通过 v 到达的最长路径
        if (dist >= d1[u]) {
            d2[u] = d1[u];
            d1[u] = dist;
        } else if (dist > d2[u]) {
            d2[u] = dist;
        }
    }
    ans = max(ans, d1[u] + d2[u]); // 经过 u 的最长路径
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dfs(1, -1);
    cout << ans << endl;
    return 0;
}

时间复杂度：O(n)
空间复杂度：O(n)

graph TD
    subgraph "以 u 为根的子树"
    U["u"] --> V1["v1 (d1[v1]+w1)"]
    U --> V2["v2 (d1[v2]+w2)"]
    U --> V3["v3 (d1[v3]+w3)"]
    end
    U -->|"d1[u] = 最大的 dist"| D1["最长路径"]
    U -->|"d2[u] = 第二大的 dist"| D2["次长路径"]
    U -->|"diameter = d1[u] + d2[u]"| ANS["经过 u 的直径"]

10.2 换根 DP（二次扫描法）¶

换根 DP（也叫 rerooting）用于解决「以每个节点为根时求某个值」的问题。

核心思想：

第一次 DFS（自底向上）：以任意节点为根，计算每棵子树的信息
第二次 DFS（自顶向下）：从根出发，利用父节点的信息更新每个节点作为根时的答案

示例：统计每个节点为根时的子树大小之和¶

问题：给定一棵 n 个节点的树，对每个节点 u，求以 u 为根时所有子树大小的总和。

graph TD
    subgraph "第一次 DFS（固定根=1）"
    A1["dp[v] = 以 v 为根的子树大小"]
    end
    subgraph "第二次 DFS（换根）"
    A2["ans[u] = ans[parent] + n - 2*dp[u]"]
    end
    A1 --> A2

转移方程（第二次 DFS）：

设 ans[u] 为以 u 为根时的子树大小总和。当根从 u 换到其子节点 v 时：

\[ans[v] = ans[u] + (n - dp[v]) - dp[v] = ans[u] + n - 2 \times dp[v]\]

+ (n - dp[v])：v 以外的节点变成了 v 的子树的一部分
- dp[v]：v 的子树不再被计入父节点 u 的子树

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
vector<int> adj[MAXN];
int dp[MAXN];     // dp[u] = 以 u 为根的子树大小（第一次 DFS）
long long ans[MAXN]; // ans[u] = 以 u 为根时的子树大小总和
int n;

// 第一次 DFS：计算子树大小
void dfs1(int u, int parent) {
    dp[u] = 1;
    for (int v : adj[u]) {
        if (v == parent) continue;
        dfs1(v, u);
        dp[u] += dp[v];
    }
}

// 第二次 DFS：换根
void dfs2(int u, int parent) {
    for (int v : adj[u]) {
        if (v == parent) continue;
        // 根从 u 换到 v
        ans[v] = ans[u] + n - 2LL * dp[v];
        dfs2(v, u);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    // 第一次 DFS，以 1 为根
    dfs1(1, -1);
    // 计算以 1 为根的答案
    for (int i = 1; i <= n; i++) ans[1] += dp[i]; // 简化版本
    // 第二次 DFS，换根
    dfs2(1, -1);
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " \n"[i == n];
    }
    return 0;
}

时间复杂度：O(n)（两次 DFS）
空间复杂度：O(n)

换根 DP 的关键

换根时只更新「受影响的部分」，而不是重新计算整个答案。这就是换根 DP 能达到 O(n) 的原因。

10.3 状压 DP¶

状态压缩 DP（简称 状压 DP）利用二进制数表示集合状态，适用于状态空间不大（通常 n ≤ 20）的问题。

10.3.1 旅行商问题 TSP¶

问题：有 n 个城市，城市之间的距离已知。一个旅行商从城市 0 出发，经过所有城市恰好一次后回到城市 0，求最短路径。

状态定义：dp[S][i] = 已经访问过集合 S 中的所有城市，当前在城市 i，的最小路径长度

其中 S 是一个二进制数，第 j 位为 1 表示城市 j 已访问。

转移方程：

\[dp[S][i] = \min_{j \in S, j \ne i} \{ dp[S \setminus \{i\}][j] + dist[j][i] \}\]

graph TD
    subgraph "状态表示"
    A["S = 0b1011（已访问城市 0, 1, 3）"]
    B["i = 3（当前在城市 3）"]
    C["dp[0b1011][3]"]
    end
    subgraph "转移"
    D["从城市 0 转来: dp[0b1001][0] + dist[0][3]"]
    E["从城市 1 转来: dp[0b1001][1] + dist[1][3]"]
    end
    A --> C
    B --> C
    C -->|"取 min"| F["最小值"]
    D --> F
    E --> F

图解：假设 4 个城市

状态 S	含义
0b0001	只访问了城市 0
0b0011	访问了城市 0, 1
0b1011	访问了城市 0, 1, 3
0b1111	全部访问

#include <bits/stdc++.h>
using namespace std;

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

    int total = 1 << n; // 总状态数 = 2^n
    // dp[S][i] = 已访问集合 S 中的城市，当前在城市 i 的最短路径
    vector<vector<int>> dp(total, vector<int>(n, INT_MAX));
    dp[1][0] = 0; // 初始状态：只访问了城市 0，当前在城市 0

    for (int S = 1; S < total; S++) {       // 枚举所有状态
        for (int i = 0; i < n; i++) {        // 枚举当前城市
            if (!(S & (1 << i))) continue;   // i 不在集合 S 中，跳过
            if (dp[S][i] == INT_MAX) continue;
            for (int j = 0; j < n; j++) {    // 枚举下一个城市
                if (S & (1 << j)) continue;  // j 已经访问过，跳过
                int newS = S | (1 << j);      // 加入城市 j
                dp[newS][j] = min(dp[newS][j], dp[S][i] + dist[i][j]);
            }
        }
    }

    // 回到城市 0
    int ans = INT_MAX;
    for (int i = 1; i < n; i++) {
        if (dp[total - 1][i] != INT_MAX) {
            ans = min(ans, dp[total - 1][i] + dist[i][0]);
        }
    }
    cout << ans << endl;
    return 0;
}

时间复杂度：O(2^n × n²)
空间复杂度：O(2^n × n)

10.3.2 棋盘覆盖¶

问题：用 1×2 的骨牌不重叠、不遗漏地铺满整个 n×m 的棋盘，求方案数。

思路：逐行处理，用二进制表示每行的填充状态，状压 DP 枚举转移。

状态定义：dp[i][S] = 前 i 行全部填满，且第 i 行的填充状态为 S 的方案数

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int total = 1 << m;

    vector<long long> dp(total, 0), ndp(total, 0);
    dp[0] = 1; // 初始状态：第 0 行之前没有格子需要填充

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            fill(ndp.begin(), ndp.end(), 0);
            for (int S = 0; S < total; S++) {
                if (dp[S] == 0) continue;
                bool cur = S & (1 << j); // 当前格子是否已被上一行的竖牌填充
                if (cur) {
                    // 当前格子已被填，直接跳到下一列
                    ndp[S ^ (1 << j)] += dp[S];
                } else {
                    // 选择 1: 放横牌（需要 j+1 < m 且下一格为空）
                    if (j + 1 < m && !(S & (1 << (j + 1)))) {
                        ndp[S | (1 << (j + 1))] += dp[S];
                    }
                    // 选择 2: 放竖牌（延伸到下一行）
                    ndp[S | (1 << j)] += dp[S];
                }
            }
            dp = ndp;
        }
    }
    cout << dp[0] << endl; // 最后一行填满后，状态应为 0
    return 0;
}

时间复杂度：O(n × m × 2^m)
空间复杂度：O(2^m)

带障碍的版本（部分格子不可用）只需把障碍格强制为不可放置状态：转移到障碍格时不放横牌、不放竖牌，直接跳过该格即可。

状压 DP 的适用场景

n ≤ 20 左右（2^20 ≈ 10^6，可接受）
每个元素只有「选/不选」两种状态，或需要记录已访问集合
经典应用：TSP、棋盘覆盖、集合划分、配对问题

10.4 数位 DP（进阶）¶

在基础章节中我们介绍了数位 DP 的基本框架。本节深入讲解数位 DP 的进阶技巧。

10.4.1 统计数字中某 digit 出现的次数¶

问题：统计 [1, n] 中数字 d 出现的总次数。

状态定义：dfs(pos, cnt, tight, lead) = 当前处理到第 pos 位，已经出现了 cnt 次数字 d，是否受上界限制，是否仍处于前导零段

前导零必须处理

若不加 lead（前导零）参数，d = 0 时会严重多计：位数不足的数会被补上前导零一起统计，例如统计 [1, 13] 时数字 5 会被当作 "05" 而多算一个 0。规则是：处于前导零段时填的 0 不计入出现次数。

#include <bits/stdc++.h>
using namespace std;

int digits[20], len;
long long dp[20][20]; // dp[pos][cnt]（仅缓存 !tight && !lead 的状态）

// 统计 [0, n] 中数字 d 出现的次数
// lead: 是否仍处于前导零段（前面填的全是 0）
long long dfs(int pos, int cnt, int d, bool tight, bool lead) {
    if (pos == len) return cnt; // 返回数字 d 出现的总次数
    if (!tight && !lead && dp[pos][cnt] != -1) return dp[pos][cnt];

    int up = tight ? digits[pos] : 9;
    long long res = 0;
    for (int dig = 0; dig <= up; dig++) {
        bool new_lead = lead && (dig == 0);
        // 关键：前导零不属于数字本身，处于前导零段时填的 0 不计数
        int new_cnt = cnt + ((dig == d && !new_lead) ? 1 : 0);
        res += dfs(pos + 1, new_cnt, d, tight && (dig == up), new_lead);
    }
    if (!tight && !lead) dp[pos][cnt] = res;
    return res;
}

long long solve(long long n, int d) {
    if (n < 0) return 0;
    len = 0;
    while (n > 0) {
        digits[len++] = n % 10;
        n /= 10;
    }
    reverse(digits, digits + len);
    memset(dp, -1, sizeof(dp));
    return dfs(0, 0, d, true, true);
}

int main() {
    long long L, R;
    int d;
    cin >> L >> R >> d;
    // [L, R] 中数字 d 出现次数 = [0, R] 中的次数 - [0, L-1] 中的次数
    cout << solve(R, d) - solve(L - 1, d) << endl;
    return 0;
}

时间复杂度：O(log n × log n × 10)（位数 × 计数 × 每位枚举）
空间复杂度：O(log n × log n)

自测样例

[1, 100] 中 0 出现 11 次（10、20、…、90 各 1 次，100 贡献 2 次）
[1, 13] 中 1 出现 6 次（1、10、12、13 各 1 次，11 贡献 2 次）

10.4.2 进阶：满足多个条件的数位 DP¶

graph TD
    A["数位 DP 状态设计"] --> B["pos: 处理到第几位"]
    A --> C["tight: 是否受上界限制"]
    A --> D["lead_zero: 是否有前导零"]
    A --> E["state: 自定义状态"]
    E --> F["各位数字之和"]
    E --> G["是否含相邻相同数字"]
    E --> H["对某数的余数"]
    E --> I["已出现的数字集合"]

数位 DP 状态设计技巧

pos 和 tight 是必有的参数
额外状态参数取决于题目限制条件
记忆化时，只有不受限的状态才能复用（因为受限状态与具体的 n 有关）

10.5 区间 DP 进阶¶

10.5.1 矩阵取数游戏（洛谷 P1005）¶

问题：给定一个 n×m 的矩阵，每行独立操作。每一行，你可以从左边或右边取数，第 i 次取到的数乘以 2^i，求总得分最大值。

关键观察：每一行独立，因此对每行分别做区间 DP。

状态定义：dp[i][j] = 还剩下第 i 到第 j 个数没取时，从现在开始能获得的最大得分

转移方程：设当前是第 k 次取数（k = m - (j - i)）

\[dp[i][j] = \max(dp[i+1][j] + a[i] \times 2^k, \; dp[i][j-1] + a[j] \times 2^k)\]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using bigint = __int128; // 需要高精度

const int MAXN = 85;
bigint dp[MAXN][MAXN];
int a[MAXN];
int n, m;

bigint solve_row() {
    memset(dp, 0, sizeof(dp));
    for (int len = 1; len <= m; len++) {
        for (int i = 1; i + len - 1 <= m; i++) {
            int j = i + len - 1;
            int k = m - len + 1; // 当前是第 k 次取数（从 m 往下倒数）
            bigint power = (bigint)1 << k; // 2^k
            dp[i][j] = max(
                dp[i + 1][j] + (bigint)a[i] * power,
                dp[i][j - 1] + (bigint)a[j] * power
            );
        }
    }
    return dp[1][m];
}

// 输出 __int128（需要手动实现）
void print_bigint(bigint x) {
    if (x == 0) { cout << 0; return; }
    string s;
    while (x > 0) {
        s += (char)('0' + x % 10);
        x /= 10;
    }
    reverse(s.begin(), s.end());
    cout << s;
}

int main() {
    cin >> n >> m;
    bigint total = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= m; j++) cin >> a[j];
        total += solve_row();
    }
    print_bigint(total);
    cout << endl;
    return 0;
}

时间复杂度：O(n × m²)
空间复杂度：O(m²)

10.5.2 区间 DP 进阶：多维状态¶

有些区间 DP 问题需要更复杂的状态设计：

graph TD
    A["区间 DP 进阶方向"] --> B["双端取数"]
    A --> C["环形区间 DP"]
    A --> D["区间 + 额外维度"]
    B --> E["每次从左端或右端取"]
    C --> F["断环成链: 复制一份拼接"]
    D --> G["dp[l][r][k]: 区间 + 额外状态"]

环形区间 DP 技巧：将长度为 n 的环断开，复制一份拼接成长度为 2n 的链，在链上做普通区间 DP，最后取所有长度为 n 的区间的最优值。

10.6 DP 优化技巧¶

当 DP 的朴素实现时间复杂度过高时，可以使用各种优化技巧。

10.6.1 滚动数组与空间压缩¶

原理：当 dp[i][...] 只依赖于 dp[i-1][...]（或前面常数行）时，没有必要保留整张二维表。常用两种写法：

写法一：滚动数组（两行交替）——用 i & 1 在两行之间交替读写，转移方程原样照抄，最不容易出错：

// 滚动数组：0-1 背包，两行交替
vector<vector<int>> dp(2, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= W; j++) {
        dp[i & 1][j] = dp[(i - 1) & 1][j]; // 不选第 i 件
        if (j >= w[i])
            dp[i & 1][j] = max(dp[i & 1][j], dp[(i - 1) & 1][j - w[i]] + v[i]);
    }
}
// 答案：dp[n & 1][W]

写法二：一维原地压缩——直接在同一个一维数组上覆盖旧值，靠遍历方向控制读到的是「上一行」还是「本行」的值（0-1 背包必须逆序）：

// 一维原地压缩：0-1 背包，逆序遍历
vector<int> dp(W + 1, 0);
for (int i = 1; i <= n; i++) {
    for (int j = W; j >= w[i]; j--) { // 逆序！保证 dp[j-w[i]] 还是上一行的值
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

压缩方向的判断：看 dp[i][j] 依赖的是上一行还是本行的数据：

graph LR
    A["dp[i][j] 依赖 dp[i-1][...]"] -->|"压缩"| B["一维 dp[j] + 逆序遍历"]
    C["dp[i][j] 依赖 dp[i-1][j-1]"] -->|"压缩"| D["一维 dp[j] + 逆序遍历"]
    E["dp[i][j] 依赖 dp[i][j-1]"] -->|"压缩"| F["一维 dp[j] + 正序遍历"]

空间从 O(n × W) 降到 O(W)，时间不变。这是最基础也最常用的优化，遍历顺序的原理已在背包 DP 章节详细讲解。

10.6.2 矩阵快速幂优化¶

原理：当 DP 的转移方程是线性递推形式时（如 dp[i] = a*dp[i-1] + b*dp[i-2] + ...），可以用矩阵快速幂将时间复杂度从 O(n) 降到 O(k³ × log n)，其中 k 是矩阵的阶数。

经典应用：求斐波那契数列第 n 项（n 可达 10^18）

朴素递推：\(F(n) = F(n-1) + F(n-2)\)，时间 O(n)

矩阵形式：

\[\begin{bmatrix} F(n) \\ F(n-1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1} \times \begin{bmatrix} F(1) \\ F(0) \end{bmatrix}\]

graph LR
    A["dp[i] = A * dp[i-1]"] --> B["矩阵形式"]
    B --> C["dp[n] = M^n * dp[0]"]
    C --> D["矩阵快速幂 O(k^3 * log n)"]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

// 矩阵乘法
vector<vector<ll>> matMul(const vector<vector<ll>>& A,
                          const vector<vector<ll>>& B) {
    int n = A.size();
    vector<vector<ll>> C(n, vector<ll>(n, 0));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++)
            for (int j = 0; j < n; j++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
}

// 矩阵快速幂
vector<vector<ll>> matPow(vector<vector<ll>> base, ll exp) {
    int n = base.size();
    vector<vector<ll>> result(n, vector<ll>(n, 0));
    for (int i = 0; i < n; i++) result[i][i] = 1; // 单位矩阵
    while (exp > 0) {
        if (exp & 1) result = matMul(result, base);
        base = matMul(base, base);
        exp >>= 1;
    }
    return result;
}

// 用矩阵快速幂求斐波那契数列第 n 项
ll fibonacci(ll n) {
    if (n <= 1) return n;
    vector<vector<ll>> M = {{1, 1}, {1, 0}};
    auto R = matPow(M, n - 1);
    return R[0][0]; // F(n) = R[0][0] * F(1) + R[0][1] * F(0) = R[0][0]
}

int main() {
    ll n;
    cin >> n;
    cout << fibonacci(n) << endl;
    return 0;
}

一般线性递推的矩阵构造：

对于递推式 \(dp[i] = c_1 \cdot dp[i-1] + c_2 \cdot dp[i-2] + \cdots + c_k \cdot dp[i-k]\)，构造转移矩阵：

\[M = \begin{bmatrix} c_1 & c_2 & \cdots & c_{k-1} & c_k \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & & \ddots & & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end{bmatrix}\]

时间复杂度：O(k³ × log n)
空间复杂度：O(k²)

矩阵快速幂适用条件

转移必须是线性的（不能有 max、min 等非线性运算）
转移矩阵必须不变（不随 i 变化）
n 必须很大（如果 n ≤ 10^6，直接递推更快）

10.6.3 单调队列优化 DP¶

原理：很多 DP 的转移方程形如

\[f[i] = \min_{i-k \le j < i} \{ f[j] \} + w[i] \quad \text{或} \quad f[i] = \max_{L(i) \le j \le R(i)} \{ g(j) \} + h(i)\]

即 f[i] 由一个随 i 单调右移的决策窗口内的最值转移而来。朴素做法每个 i 都把窗口扫一遍，总时间 O(nk)；注意到这正是「滑动窗口最值」问题——用单调队列（单调双端队列）维护窗口内的候选决策，每个下标至多入队、出队一次，总时间降为 O(n)。

前提：把转移拆成「只与 j 有关的部分 g(j)」+「只与 i 有关的部分 h(i)」，队列里维护的是 g(j) 的最值。

模板（以求 max 为例，队首到队尾 g(j) 单调递减）：

deque<int> q; // 存决策下标 j
for (int i = 1; i <= n; i++) {
    while (!q.empty() && q.front() < L(i)) q.pop_front();   // 1. 队首出窗（过期决策）
    f[i] = g(q.front()) + h(i);                              // 2. 队首即当前最优决策
    while (!q.empty() && g(q.back()) <= g(i)) q.pop_back();  // 3. 队尾弹出不如 i 的决策
    q.push_back(i);                                          //    i 作为未来的决策入队
}

时间复杂度：O(n)（每个下标均摊 O(1)）
空间复杂度：O(n)

例题：修剪草坪（洛谷 P2627 [USACO11OPEN] Mowing the Lawn G）¶

题意：n 头奶牛排成一行，第 i 头的效率为 E[i]（非负）。选出若干头奶牛，要求不能有超过 K 头连续被选中，最大化效率之和。n ≤ 10^5。

思路（正难则反）：「连续选中不超过 K 头」等价于「每 K+1 个连续位置中至少有一头不选」，于是枚举不选哪些牛。

状态定义：f[i] = 第 i 头牛不选、只考虑前 i 头牛时的最大效率和（引入虚拟的第 0 头牛，f[0] = 0）。

转移方程：设上一头不选的牛是 j，则 j+1 .. i-1 全部被选，需满足 i - j - 1 ≤ K。记前缀和 s[i]：

\[f[i] = \max_{i-K-1 \le j \le i-1} \{ f[j] + s[i-1] - s[j] \} = s[i-1] + \max_{i-K-1 \le j \le i-1} \{ \underbrace{f[j] - s[j]}_{g(j)} \}\]

窗口长度固定为 K+1，用单调队列维护 g(j) = f[j] - s[j] 的最大值即可。

答案：最后一头不选的牛 j 之后全选，需 n - j ≤ K：ans = max{ f[j] + s[n] - s[j] : n-K ≤ j ≤ n }。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n, k;
    cin >> n >> k;
    vector<ll> s(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        ll e;
        cin >> e;
        s[i] = s[i - 1] + e; // 前缀和
    }
    // f[i] = 第 i 头牛不选、只考虑前 i 头牛时的最大效率和（f[0] 为虚拟起点）
    vector<ll> f(n + 1, 0);
    deque<int> q;   // 存决策下标 j，g(j) = f[j] - s[j] 从队首到队尾递减
    q.push_back(0);
    for (int i = 1; i <= n; i++) {
        while (!q.empty() && q.front() < i - k - 1) q.pop_front(); // 1. 队首出窗
        int j = q.front();
        f[i] = f[j] - s[j] + s[i - 1];                             // 2. 队首即最优决策
        while (!q.empty() && f[q.back()] - s[q.back()] <= f[i] - s[i])
            q.pop_back();                                          // 3. 队尾维护单调性
        q.push_back(i);
    }
    ll ans = 0;
    for (int j = max(0, n - k); j <= n; j++)
        ans = max(ans, f[j] + s[n] - s[j]);
    cout << ans << endl;
    return 0;
}

样例：n=5, K=2, E = [1, 2, 3, 4, 5]，输出 12（选第 1、2、4、5 头，跳过第 3 头）。同类练习：洛谷 P1725 琪露诺（转移 \(f[i] = \max_{i-R \le j \le i-L} f[j] + a[i]\)，窗口两端都在滑动）。

时间复杂度：O(n)
空间复杂度：O(n)

单调队列优化的常见坑

队列里维护的是 g(j) = f[j] - s[j]，不是 f[j]——先把与 i 无关的部分分离出来再上队列
窗口下界是 i-K-1 而不是 i-K：枚举的是「不选」的位置，两个不选位置之间最多夹 K 个连选
决策 i 必须在算完 f[i] 之后入队（f[i] 只能由更早的决策转移而来）
该优化要求决策窗口随 i 单调滑动；若窗口下界不单调，单调队列会错误地永久丢弃决策

10.6.4 斜率优化 DP（入门）¶

引入：转移形如 \(f[i] = \min_j \{ f[j] + cost(j, i) \}\)，当 cost 中出现 i 与 j 的乘积项（典型如平方式 \((s[i]-s[j])^2\) 展开后的 \(-2s[i]s[j]\)）时，min 里每一项都同时依赖 i 和 j，无法像上一节那样把 g(j) 拆出来用单调队列直接维护。这时把每个决策 j 看作平面上的点，把转移整理成一次函数，用下凸壳筛选可能的最优决策——这就是斜率优化（凸壳优化）。

载体例题：玩具装箱（洛谷 P3195 [HNOI2008]）¶

题意：n 个玩具排成一行，第 i 个长度为 C[i]。可以把连续一段 [j+1, i] 装进一个容器，容器长度 \(x = (i - j - 1) + \sum_{k=j+1}^{i} C_k\)，费用为 \((x - L)^2\)。把所有玩具装完，求最小总费用。n ≤ 5×10^4。

第一步：整理转移方程。记 \(s[i] = \sum_{k \le i} C_k + i\)（前缀和加上件数），\(L' = L + 1\)，则段 [j+1, i] 的费用恰为 \((s[i] - s[j] - L')^2\)：

\[f[i] = \min_{0 \le j < i} \{ f[j] + (s[i] - s[j] - L')^2 \}\]

第二步：推导一次函数形式。令 \(a_i = s[i] - L'\)（只与 i 有关），展开平方：

\[f[i] = f[j] + s[j]^2 - 2 a_i \cdot s[j] + a_i^2\]

把每个决策 j 看作平面上的点 \((x_j, y_j) = (s[j],\; f[j] + s[j]^2)\)，上式变形为：

\[y_j = \underbrace{2 a_i}_{\text{斜率 } k_i} \cdot x_j + \underbrace{(f[i] - a_i^2)}_{\text{截距 } b_i}\]

求 f[i] 最小 ⟺ 截距 \(b_i\) 最小 ⟺ 用一条斜率为 \(k_i = 2a_i\) 的直线从下往上平移，第一个碰到的决策点即最优——它一定落在所有决策点的下凸壳上。

第三步：单调队列维护下凸壳。本题中 \(C_i > 0\)，故 \(x_j = s[j]\) 严格递增；查询斜率 \(k_i = 2a_i\) 也随 i 单调递增。于是凸壳可用单调队列 O(n) 维护：

队首：壳上相邻两点连线斜率 ≤ \(k_i\) 时，左端点不再可能最优，弹出队首
队尾：新点加入破坏下凸性（左边斜率 ≥ 右边斜率）时，弹出队尾

graph LR
    A["f[i] = min f[j] + cost(j,i)"] --> B["展开，分离 i 项与 j 项"]
    B --> C["整理成 y_j = k_i · x_j + b_i"]
    C --> D["决策点 (x_j, y_j) 维护下凸壳"]
    D --> E["k_i 单调 → 单调队列 O(n)"]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 50005;
int n;
ll L, s[MAXN], f[MAXN];
int q[MAXN]; // 手写单调队列，存下凸壳上的决策下标

ll X(int j) { return s[j]; }                       // 决策点横坐标
__int128 Y(int j) {                                // 决策点纵坐标（可能超 long long）
    return (__int128)f[j] + (__int128)s[j] * s[j];
}

// slope(a, b) <= k ？交叉相乘避免除法（X 严格递增，X(b) > X(a)）
bool slopeLE(int a, int b, ll k) {
    return Y(b) - Y(a) <= (__int128)k * (X(b) - X(a));
}
// 加入新点 c 后，队尾点 b 是否不再在下凸壳上（用 >= 顺便弹掉共线点）
bool notConvex(int a, int b, int c) {
    return (Y(b) - Y(a)) * (X(c) - X(b)) >= (Y(c) - Y(b)) * (X(b) - X(a));
}

int main() {
    cin >> n >> L;
    L++; // L' = L + 1
    for (int i = 1; i <= n; i++) {
        ll c;
        cin >> c;
        s[i] = s[i - 1] + c;
    }
    for (int i = 1; i <= n; i++) s[i] += i; // s[i] = 前缀和 + i
    int head = 0, tail = 0;
    q[tail++] = 0; // 初始决策 j = 0
    for (int i = 1; i <= n; i++) {
        ll a = s[i] - L; // a_i = s[i] - L'
        // 队首：斜率 <= 2*a_i 的壳边，其左端点不再可能最优
        while (tail - head >= 2 && slopeLE(q[head], q[head + 1], 2 * a)) head++;
        int j = q[head];
        f[i] = f[j] + (a - s[j]) * (a - s[j]);
        // 队尾：维护下凸性
        while (tail - head >= 2 && notConvex(q[tail - 2], q[tail - 1], i)) tail--;
        q[tail++] = i;
    }
    cout << f[n] << endl;
    return 0;
}

样例：n=5, L=4, C = [3, 4, 2, 1, 4]，输出 1（分段 {1}、{2}、{3,4}、{5}，费用 1+0+0+0）。

时间复杂度：O(n)（每个决策至多入队、出队一次）
空间复杂度：O(n)

斜率优化的常见坑

斜率比较避免除法：交叉相乘时乘积可能超出 long long（本题 \(y_j = f[j]+s[j]^2\) 可达 \(10^{23}\) 量级），用 __int128（long double 有精度风险）
弹队尾判凸性用 >=：顺便弹掉共线点，避免后续斜率比较出现除零式的退化情形
预处理别错：s[i] 里要加上 i、L 要加 1，这一步错了后面全错
本节是入门级推导，依赖两个单调性：\(x_j\) 单调递增、查询斜率 \(k_i\) 单调递增。若 \(k_i\) 不单调需在凸壳上二分查找；若 \(x_j\) 也不单调需 CDQ 分治或平衡树动态维护凸壳，深入内容见进阶资料

10.6.5 优化技巧总结¶

优化方法	适用场景	复杂度变化
滚动数组 / 空间压缩	dp[i] 只依赖前常数行	空间 O(nW) → O(W)
矩阵快速幂	线性递推，n 极大	时间 O(n) → O(k³ log n)
单调队列优化	决策区间为滑动窗口	时间 O(nk) → O(n)
斜率优化	转移可整理为一次函数 + 凸壳	时间 O(n²) → O(n)
四边形不等式	区间 DP，cost 满足四边形不等式	时间 O(n³) → O(n²)

DP 优化的学习建议

先掌握朴素 DP，确保状态和转移方程正确
再根据数据范围选择合适的优化
矩阵快速幂是面试和竞赛中最常考的优化技巧
单调队列优化和斜率优化的入门讲解见 10.6.3 / 10.6.4，核心都是「把只与 j 有关的部分分离出来」，建议配合例题反复体会
四边形不等式优化本手册暂不展开，可在掌握前两者后再学习

总结¶

mindmap
  root((动态规划进阶))
    树形 DP
      没有上司的舞会
      树的直径
      子树信息汇总
    换根 DP
      二次扫描法
      自底向上 + 自顶向下
    状压 DP
      TSP 旅行商
      棋盘覆盖
      集合枚举
    数位 DP 进阶
      多条件统计
      状态设计技巧
    区间 DP 进阶
      矩阵取数游戏
      环形区间 DP
    DP 优化
      滚动数组与空间压缩
      矩阵快速幂
      单调队列优化
      斜率优化

进阶 DP 学习建议

树形 DP 是面试高频题，务必多练
状压 DP 的关键是熟练使用位运算
数位 DP 需要大量练习才能掌握状态设计
矩阵快速幂是竞赛中的「大杀器」，模板要背熟
遇到新题型时，先想朴素 DP，再考虑优化

更远的方向：期望 / 概率 DP

本章之外，期望 / 概率 DP（状态值为期望或概率，典型如 AtCoder DP 专题 J 题 Sushi）也是常见的进阶方向，本手册暂不展开，学完本章后可自行练习。

练习题¶

ACM Day5 - DP 进阶¶

题号	平台	题目	难度	链接	完成
1946C	CF	Tree Cutting	1600	链接	- [ ]
2070D	CF	Tree Jumps	1600	链接	- [ ]
1970C2	CF	Game on Tree (Medium)	1700	链接	- [ ]
2133D	CF	Chicken Jockey	1900	链接	- [ ]
1990D	CF	Grid Puzzle	1800	链接	- [ ]
1912K	CF	Kim's Quest	1800	链接	- [ ]
2192D	CF	Cost of Tree	1800	链接	- [ ]
dp_n	AT	Slimes	—	链接	- [ ]
dp_u	AT	Groups	—	链接	- [ ]
dp_r	AT	Walk	—	链接	- [ ]
P1005	洛谷	矩阵取数游戏	—	链接	- [ ]
P1352	洛谷	没有上司的舞会	—	链接	- [ ]

附录：DP 分类速查表¶

DP 类型	核心特征	典型例题	时间复杂度
线性 DP	沿序列递推	LIS、LCS、编辑距离	O(n) ~ O(n²)
背包 DP	选或不选物品	0-1背包、完全背包	O(nW)
区间 DP	区间 [i, j] 分割	石子合并、戳气球	O(n³)
树形 DP	树上递归	没有上司的舞会	O(n)
换根 DP	两次 DFS	每个节点为根的最优值	O(n)
状压 DP	二进制表示集合	TSP、棋盘覆盖	O(2^n × n²)
数位 DP	逐位枚举	统计数字个数	O(log n × states)
矩阵快速幂	线性递推加速	斐波那契第 n 项	O(k³ log n)

第 10 章 动态规划进阶¶