第四章动态规划（进阶）—— 区间DP + 状压DP + 树形DP#

一句话理解：基础 DP 处理的是”线性递推”，进阶 DP 处理的是”区间合并”、“集合状态”和”树上的信息汇聚”——状态定义从一维跃升到更高维度，但三要素的本质不变。

📋 前置知识：Ch3（基础DP）、数据结构 Ch6（树）、Ch9（并查集）

4.1 概念直觉 —— 三类进阶 DP 的共性#

基础 DP 的状态通常是 dp[i]（前 i 个），转移只依赖相邻的前几个状态。进阶 DP 的状态空间更复杂：

1
区间 DP：   dp[l][r]   —— 区间 [l, r] 上的最优解
2
状压 DP：   dp[mask]   —— mask 的二进制位表示集合
3
树形 DP：   dp[node]   —— 以 node 为根的子树上的最优解

三者的共同特征：状态的定义不再是一维线性，而是结构化的一维（区间/集合/树节点）。这导致它们的遍历顺序不再是简单的 for i from 0 to n。

4.2 区间 DP —— 从短到长合并#

核心模板#

区间 DP 处理”一段区间上的最优解”，其核心是枚举区间的分割点。

1
模板：
2
for len = 2 to n:                    // 区间长度从小到大
3
  for l = 0 to n-len:                // 区间起点
4
    r = l + len - 1                   // 区间终点
5
    for k = l to r-1:                 // 枚举分割点
6
      dp[l][r] = merge(dp[l][k], dp[k+1][r])

⚠️ 遍历顺序是关键：必须按区间长度递增，而不能按 l 递增。因为 dp[l][r] 依赖更短区间的结果，而 dp[l+1][r] 恰好比 dp[l][r] 短——只有按长度遍历才能保证依赖的状态已计算好。

graph TD subgraph "区间 DP 的遍历顺序" direction LR L1["len=1: dp[0][0], dp[1][1], ..., dp[n-1][n-1]\n(单个元素，初始状态)"] L2["len=2: dp[0][1], dp[1][2], ..., dp[n-2][n-1]"] L3["len=3: dp[0][2], dp[1][3], ..."] L4["..."] L5["len=n: dp[0][n-1] ← 最终答案"] end style L1 fill:#555,stroke:#888,color:#ccc style L5 fill:#d00000,stroke:#e85d04,color:white

戳气球 (LeetCode 312)#

1
问题：n 个气球排成一排，戳破第 i 个得 nums[i-1]*nums[i]*nums[i+1] 分。
2
求最大得分。首尾边界视为 1。
3

4
关键洞察：正向思考"先戳哪个"很复杂（戳破后邻居会变）。
5
逆向思考：最后一个戳破的气球——它的左右两部分是独立子问题！

1
int maxCoins(std::vector<int>& nums) {
2
    int n = nums.size();
3
    // 首尾补 1，简化边界处理
4
    std::vector<int> val(n + 2, 1);
5
    for (int i = 0; i < n; ++i) val[i + 1] = nums[i];
6

7
    // dp[l][r] = 戳破开区间 (l, r) 内所有气球的最大得分
8
    // 注意：(l, r) 是开区间——l 和 r 位置的气球保留不戳
9
    std::vector<std::vector<int>> dp(n + 2, std::vector<int>(n + 2, 0));
10

11
    // 按区间长度递增
12
    for (int len = 3; len <= n + 2; ++len) {  // 至少包含一个气球
13
        for (int l = 0; l + len - 1 <= n + 1; ++l) {
14
            int r = l + len - 1;
15
            // 枚举 (l, r) 中最后被戳破的气球 k
16
            for (int k = l + 1; k < r; ++k) {
17
                // k 是最后一个 → 此时 l 和 r 都还在
18
                int coins = val[l] * val[k] * val[r];
19
                dp[l][r] = std::max(dp[l][r],
20
                    dp[l][k] + dp[k][r] + coins);
21
            }
22
        }
23
    }
24
    return dp[0][n + 1];  // 开区间 (0, n+1) = 所有气球
25
}

graph TD subgraph "戳气球：逆向思考" direction TB Start["dp[l][r] = 戳破 (l,r) 内所有气球的最大分"] Split["枚举最后戳破的气球 k\nl < k < r"] Left["dp[l][k]\n左半独立子问题"] Right["dp[k][r]\n右半独立子问题"] Bonus["val[l] * val[k] * val[r]\nk 最后被戳时的得分"] Start --> Split Split --> Left Split --> Right Split --> Bonus end style Start fill:#d00000,stroke:#e85d04,color:white style Split fill:#e85d04,stroke:#f48c06,color:white style Left fill:#2d6a4f,stroke:#40916c,color:white style Right fill:#2d6a4f,stroke:#40916c,color:white

💡 面试中的表述：「戳气球的难点在于正向思考时邻居会动态变化。关键思维跃迁是反向思考——最后一个戳破的气球，其左右两侧的所有气球都已被戳破，形成两个完全独立的子问题。这种”枚举最后一步”的逆向思维是区间 DP 的核心技巧。」

石子游戏 (LeetCode 877)#

1
// dp[l][r] = 在 piles[l..r] 上，先手比后手多得的石头数
2
// 先手可以选 piles[l] 或 piles[r]：
3
//   - 选 piles[l]：得到 piles[l]，然后对方在 [l+1, r] 上成为先手
4
//   - 选 piles[r]：得到 piles[r]，然后对方在 [l, r-1] 上成为先手
5
bool stoneGame(std::vector<int>& piles) {
6
    int n = piles.size();
7
    std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
8

9
    for (int i = 0; i < n; ++i) dp[i][i] = piles[i];
10

11
    for (int len = 2; len <= n; ++len) {
12
        for (int l = 0; l + len - 1 < n; ++l) {
13
            int r = l + len - 1;
14
            dp[l][r] = std::max(
15
                piles[l] - dp[l + 1][r],  // 选左，减去对方在剩余区间上的优势
16
                piles[r] - dp[l][r - 1]   // 选右
17
            );
18
        }
19
    }
20
    return dp[0][n - 1] > 0;
21
}

这题其实可以直接 return true（数学上 Alex 总能赢），但面试中写出 DP 解法更重要。

奇怪的打印机 (LeetCode 664)#

1
// dp[l][r] = 打印 s[l..r] 的最少次数
2
// 如果 s[l] == s[k]（k ∈ [l+1, r]），则 s[l] 可以和 s[k] 一起打印
3
int strangePrinter(std::string s) {
4
    int n = s.size();
5
    std::vector<std::vector<int>> dp(n, std::vector<int>(n, n));
6
    for (int i = 0; i < n; ++i) dp[i][i] = 1;
7

8
    for (int len = 2; len <= n; ++len) {
9
        for (int l = 0; l + len - 1 < n; ++l) {
10
            int r = l + len - 1;
11
            // 策略 1：单独打 s[l]，然后打 s[l+1..r]
12
            dp[l][r] = 1 + dp[l + 1][r];
13
            // 策略 2：如果 s[l] == s[k]，s[l] 可以顺便带出来
14
            for (int k = l + 1; k <= r; ++k) {
15
                if (s[l] == s[k]) {
16
                    dp[l][r] = std::min(dp[l][r],
17
                        dp[l][k - 1] + (k + 1 <= r ? dp[k + 1][r] : 0));
18
                }
19
            }
20
        }
21
    }
22
    return dp[0][n - 1];
23
}

4.3 状态压缩 DP —— 用 bitmask 表示集合#

当问题涉及”元素的选取状态”且 n ≤ 20 时，状态压缩 DP 是最优选择。核心是用 int 的二进制位表示集合。

1
基础操作速查：
2
mask | (1 << i)       —— 加入元素 i
3
mask & ~(1 << i)      —— 移除元素 i
4
mask & (1 << i)       —— 检查元素 i 是否在集合中
5
mask ^ (1 << i)       —— 翻转元素 i 的状态
6
__builtin_popcount(mask) —— 集合大小（GCC 内置）

旅行商问题 TSP#

1
问题：N 个城市，求从 0 出发、每个城市恰好访问一次后回到 0 的最短路径。
2

3
状态定义：
4
  dp[mask][i] = 已访问城市集合为 mask，当前在城市 i 的最短距离
5

6
转移：
7
  dp[mask][i] = min(dp[mask\{i}][j] + dist[j][i])  其中 j ∈ mask\{i}
8

9
复杂度：O(n² * 2ⁿ)

1
int tsp(const std::vector<std::vector<int>>& dist) {
2
    int n = dist.size();
3
    int FULL = (1 << n) - 1;
4

5
    // dp[mask][i] = 已访问集合 mask，最后一个城市是 i
6
    std::vector<std::vector<int>> dp(1 << n, std::vector<int>(n, INT_MAX / 2));
7

8
    dp[1][0] = 0;  // 只访问了城市 0
9

10
    for (int mask = 1; mask <= FULL; ++mask) {
11
        for (int i = 0; i < n; ++i) {
12
            if (!(mask & (1 << i))) continue;  // i 必须在 mask 中
13

14
            int prevMask = mask ^ (1 << i);     // 去掉 i
15
            for (int j = 0; j < n; ++j) {
16
                if (!(prevMask & (1 << j))) continue;
17
                dp[mask][i] = std::min(dp[mask][i],
18
                    dp[prevMask][j] + dist[j][i]);
19
            }
20
        }
21
    }
22

23
    // 回到起点
24
    int ans = INT_MAX;
25
    for (int i = 1; i < n; ++i) {
26
        ans = std::min(ans, dp[FULL][i] + dist[i][0]);
27
    }
28
    return ans;
29
}

graph TD subgraph "TSP 状态转移示意图" direction LR S1["mask={0,2}, i=2\ndp[101][2]"] -->|"来自"| S2["mask={0}, j=0\ndp[001][0] + dist[0][2]"] S2 -->|"也可到达"| S3["mask={0,2,3}, i=3\ndp[101][2] + dist[2][3]"] end style S1 fill:#e85d04,stroke:#f48c06,color:white style S2 fill:#2d6a4f,stroke:#40916c,color:white style S3 fill:#d00000,stroke:#e85d04,color:white

划分为 k 个相等的子集 (LeetCode 698)#

1
// 能否将数组分成 k 个和相等的子集？
2
// n ≤ 16 → 状压 DP
3
bool canPartitionKSubsets(std::vector<int>& nums, int k) {
4
    int sum = std::accumulate(nums.begin(), nums.end(), 0);
5
    if (sum % k != 0) return false;
6

7
    int target = sum / k;
8
    int n = nums.size();
9
    int FULL = (1 << n) - 1;
10

11
    // dp[mask] = 当前已选集合为 mask 时，当前正在填充的子集的当前和
12
    // dp[mask] == 0 表示刚好填满了一个子集，从下一个开始
13
    std::vector<int> dp(1 << n, -1);
14
    dp[0] = 0;
15

16
    for (int mask = 0; mask <= FULL; ++mask) {
17
        if (dp[mask] == -1) continue;
18

19
        for (int i = 0; i < n; ++i) {
20
            if (mask & (1 << i)) continue;
21
            int nextSum = dp[mask] + nums[i];
22
            if (nextSum <= target) {
23
                dp[mask | (1 << i)] = (nextSum == target) ? 0 : nextSum;
24
            }
25
        }
26
    }
27
    return dp[FULL] != -1;
28
}

并行课程 II (LeetCode 1494)#

1
// n 门课，有先修关系和每学期最多选 k 门的限制
2
// 状压 DP：dp[mask] = 修完 mask 集合所需的最少学期数
3
int minNumberOfSemesters(int n, std::vector<std::vector<int>>& relations, int k) {
4
    // pre[i] = 课程 i 的先修课集合
5
    std::vector<int> pre(n, 0);
6
    for (const auto& r : relations) {
7
        int from = r[0] - 1, to = r[1] - 1;
8
        pre[to] |= (1 << from);
9
    }
10

11
    int FULL = (1 << n) - 1;
12
    std::vector<int> dp(1 << n, n + 1);
13
    dp[0] = 0;
14

15
    for (int mask = 0; mask <= FULL; ++mask) {
16
        if (dp[mask] == n + 1) continue;
17

18
        // 找出当前可以选的课：先修课都已完成
19
        int available = 0;
20
        for (int i = 0; i < n; ++i) {
21
            if (!(mask & (1 << i)) && (mask & pre[i]) == pre[i]) {
22
                available |= (1 << i);
23
            }
24
        }
25

26
        // 枚举 available 的大小 <= k 的子集（Gosper's Hack）
27
        for (int sub = available; sub; sub = (sub - 1) & available) {
28
            if (__builtin_popcount(sub) > k) continue;
29
            dp[mask | sub] = std::min(dp[mask | sub], dp[mask] + 1);
30
        }
31
    }
32
    return dp[FULL];
33
}

💡 for (int sub = mask; sub; sub = (sub - 1) & mask) 是枚举 mask 的所有非空子集的标准写法。总复杂度 O(3ⁿ)，因为每个元素在子集枚举中有三种状态：在 mask、在 sub、都不在。

4.4 树形 DP —— 后序遍历的信息汇聚#

树形 DP 天然配合后序遍历：先处理完左右子树，再处理当前节点。

二叉树中的最大路径和 (LeetCode 124)#

1
// 路径：树上任意两个节点之间的唯一通路
2
// 对每个节点：以其为"拐点"的最大路径和 = 左路径贡献 + 右路径贡献 + 自身值
3
int maxPathSum(TreeNode* root) {
4
    int ans = INT_MIN;
5

6
    // dfs(node) = 以 node 为起点、向下延伸的单边最大路径和
7
    std::function<int(TreeNode*)> dfs = [&](TreeNode* node) -> int {
8
        if (!node) return 0;
9

10
        int leftGain  = std::max(0, dfs(node->left));   // 负贡献不如不走
11
        int rightGain = std::max(0, dfs(node->right));
12

13
        // 以 node 为拐点的路径
14
        ans = std::max(ans, node->val + leftGain + rightGain);
15

16
        // 返回单边最大值（给父节点使用）
17
        return node->val + std::max(leftGain, rightGain);
18
    };
19

20
    dfs(root);
21
    return ans;
22
}

graph TD subgraph "树形 DP 的信息流向" direction TB Root["root"] --> L["左子树返回\nleftGain"] Root --> R["右子树返回\nrightGain"] L --> Ans["拐点路径 = val + leftGain + rightGain\n(更新全局答案)"] R --> Ans L --> Up["向上返回 = val + max(leftGain, rightGain)\n(单边最大值)"] R --> Up end style Root fill:#d00000,stroke:#e85d04,color:white style Ans fill:#2d6a4f,stroke:#40916c,color:white style Up fill:#e85d04,stroke:#f48c06,color:white

打家劫舍 III (LeetCode 337)#

1
// 树上版本：不能偷相邻节点（父子关系）
2
// 对每个节点返回两个值：
3
//   rob[node]   = 偷 node 时的最大收益
4
//   skip[node]  = 不偷 node 时的最大收益
5
int rob(TreeNode* root) {
6
    // 返回 pair: {偷当前节点, 不偷当前节点}
7
    std::function<std::pair<int,int>(TreeNode*)> dfs =
8
        [&](TreeNode* node) -> std::pair<int,int> {
9
        if (!node) return {0, 0};
10

11
        auto [lRob, lSkip] = dfs(node->left);
12
        auto [rRob, rSkip] = dfs(node->right);
13

14
        int robCur  = node->val + lSkip + rSkip;          // 偷当前 → 子节点不能偷
15
        int skipCur = std::max(lRob, lSkip) + std::max(rRob, rSkip); // 不偷 → 子节点可选
16

17
        return {robCur, skipCur};
18
    };
19

20
    auto [robRoot, skipRoot] = dfs(root);
21
    return std::max(robRoot, skipRoot);
22
}

树的最小支配集 (简介)#

1
问题：选择最少的节点，使得每个节点要么被选中，要么与一个选中节点相邻。
2

3
树形 DP 三状态：
4
  dp[node][0] = node 被选中 → 子树都已被覆盖
5
  dp[node][1] = node 未被选中，但被某个子节点覆盖
6
  dp[node][2] = node 未被选中，也没被子节点覆盖（需要父节点覆盖）

4.5 DP 优化技巧#

滚动数组回顾#

基础 DP 已覆盖。这里补充一个通用原则：dp[i] 依赖 dp[i-1] 和 dp[i-2] → 用两个变量；依赖上一行整行 → 用两行滚动；依赖前 K 行 → 用 K+1 行滚动。

单调队列优化 DP#

当转移方程形如 dp[i] = max(dp[j] + f(i)) 且 j 在一个滑动窗口内时，可以用单调队列优化。

1
// 例题：跳跃游戏 VI (LeetCode 1696)
2
// dp[i] = nums[i] + max(dp[j])  其中 i-k ≤ j < i
3
// 朴素是 O(nk)，单调队列优化到 O(n)
4
int maxResult(std::vector<int>& nums, int k) {
5
    int n = nums.size();
6
    std::vector<int> dp(n);
7
    dp[0] = nums[0];
8

9
    // 单调递减队列：存索引，保证 dp 值从大到小
10
    std::deque<int> dq;
11
    dq.push_back(0);
12

13
    for (int i = 1; i < n; ++i) {
14
        // 移除过期的（超出窗口 k）
15
        while (!dq.empty() && dq.front() < i - k) {
16
            dq.pop_front();
17
        }
18

19
        dp[i] = nums[i] + dp[dq.front()];
20

21
        // 维护单调递减：新来的 dp[i] 比队尾大，队尾就没用了
22
        while (!dq.empty() && dp[dq.back()] <= dp[i]) {
23
            dq.pop_back();
24
        }
25
        dq.push_back(i);
26
    }
27
    return dp[n - 1];
28
}

💡 面试中的表述：「单调队列优化 DP 的核心在于——当转移只依赖滑动窗口内的最值时，用单调队列 O(1) 维护最值，替代 O(k) 的扫描。常见信号：转移方程中有 max/min(dp[j])，且 j 的范围是一个随 i 滑动的窗口。」

斜率优化简介#

当转移方程形如 dp[i] = min(dp[j] + a[i]*b[j] + c[i])，可以看作直线方程，用凸包 + 二分优化到 O(n log n)。这是竞赛级别的技巧，面试中极少直接要求手写，但了解其存在可以在讨论优化时展现深度。

4.6 DP 类型识别与选型#

面试中看到题目的第一分钟，决定它是 DP 后，第二分钟就要锁定 DP 类型。

1
识别 Checklist：
2

3
□ 状态是否可以用"区间"描述？
4
   → 区间 DP。信号：合并、戳破、消除、回文、游戏博弈
5
   → 遍历顺序：按长度递增
6

7
□ 元素数量 n ≤ 20，涉及"选了哪些"？
8
   → 状压 DP。信号：TSP、子集划分、状态覆盖、分配问题
9
   → 遍历顺序：按 mask 递增（自动保证子集先于超集）
10

11
□ 数据结构是树，问题与子树相关？
12
   → 树形 DP。信号：子树最值、路径、打家劫舍树上版
13
   → 遍历顺序：后序遍历（子 → 父）
14

15
□ 转移中有滑动窗口内的 max/min(dp[j])？
16
   → 单调队列优化。信号：dp[i] 依赖前 k 个状态的最值
17

18
□ 其他情况？
19
   → 线性 DP / 背包（回 Ch3），或不是 DP（贪心 / 回溯 → 后续章节）

4.7 高频面试题精讲#

题目 1：不同路径 III (LeetCode 980)#

在网格上从起点到终点，要求经过所有空格恰好一次。求路径数。

1
// 网格大小 ≤ 20 → 状压 DP
2
// 也可以用 DFS 回溯（Ch6 会讲），这里展示状压写法
3
int uniquePathsIII(std::vector<std::vector<int>>& grid) {
4
    int m = grid.size(), n = grid[0].size();
5
    int startR, startC, endR, endC;
6
    int emptyCount = 0;
7

8
    // 编码：把 (r,c) 映射为 [0, m*n)
9
    auto encode = [n](int r, int c) { return r * n + c; };
10

11
    for (int r = 0; r < m; ++r) {
12
        for (int c = 0; c < n; ++c) {
13
            if (grid[r][c] == 1)      { startR = r; startC = c; }
14
            else if (grid[r][c] == 2) { endR = r; endC = c; }
15
            if (grid[r][c] != -1)     { ++emptyCount; }
16
        }
17
    }
18

19
    int cells = m * n;
20
    int FULL = (1 << cells) - 1;
21
    int dirs[] = {0, 1, 0, -1, 0};
22

23
    // dp[mask][pos] = 到达位置 pos，已访问集合为 mask 的路径数
24
    std::vector<std::vector<int>> dp(1 << cells,
25
        std::vector<int>(cells, 0));
26

27
    int startMask = 1 << encode(startR, startC);
28
    dp[startMask][encode(startR, startC)] = 1;
29

30
    int ans = 0;
31
    for (int mask = 0; mask <= FULL; ++mask) {
32
        if (__builtin_popcount(mask) > emptyCount) continue;
33

34
        for (int r = 0; r < m; ++r) {
35
            for (int c = 0; c < n; ++c) {
36
                int pos = encode(r, c);
37
                if (dp[mask][pos] == 0) continue;
38

39
                if (r == endR && c == endC &&
40
                    __builtin_popcount(mask) == emptyCount) {
41
                    ans += dp[mask][pos];
42
                    continue;
43
                }
44

45
                for (int d = 0; d < 4; ++d) {
46
                    int nr = r + dirs[d], nc = c + dirs[d + 1];
47
                    if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
48
                    if (grid[nr][nc] == -1) continue;
49

50
                    int npos = encode(nr, nc);
51
                    if (mask & (1 << npos)) continue;  // 已访问
52

53
                    dp[mask | (1 << npos)][npos] += dp[mask][pos];
54
                }
55
            }
56
        }
57
    }
58
    return ans;
59
}

4.8 🎮 游戏实战#

4.8.1 合成系统的最优策略 —— 区间 DP#

游戏中，三件低级装备可以合成一件高级装备，但不同合成顺序影响最终属性。

1
// N 件材料排成一排，每次合并相邻的三件，产生一件新装备
2
// 属性值 = 三件材料属性之和 * 合成系数
3
// 求最大属性值 → 区间 DP（与戳气球同模板）
4
struct Material {
5
    int atk, def, spd;
6
    int score() const { return atk + def + spd; }
7
};
8

9
int optimalCraft(const std::vector<Material>& materials) {
10
    int n = materials.size();
11
    // dp[l][r] = 将 [l, r] 内所有材料合成为一件的最大评分
12
    std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
13

14
    for (int i = 0; i < n; ++i) dp[i][i] = materials[i].score();
15

16
    for (int len = 2; len <= n; ++len) {
17
        for (int l = 0; l + len - 1 < n; ++l) {
18
            int r = l + len - 1;
19
            for (int k = l; k < r; ++k) {
20
                // 将 [l,k] 和 [k+1,r] 的合成结果再合成
21
                // 合成系数随等级提升
22
                int level = len / 3 + 1;
23
                dp[l][r] = std::max(dp[l][r],
24
                    dp[l][k] + dp[k + 1][r] + level * 10);
25
            }
26
        }
27
    }
28
    return dp[0][n - 1];
29
}

4.8.2 技能树解锁规划 —— 状压 DP#

1
// N 个技能节点，有前置依赖（DAG），每个技能有学习成本和战斗力提升
2
// 给定总技能点数，求最大战斗力 →
3
// 状压 DP：mask 表示已学习的技能集合
4
struct SkillNode {
5
    int cost;        // 学习消耗的技能点
6
    int power;       // 战斗力提升
7
    int prerequisites; // 前置技能的 bitmask
8
};
9

10
int maxPower(const std::vector<SkillNode>& skills, int totalPoints) {
11
    int n = skills.size();
12
    int FULL = (1 << n) - 1;
13

14
    // dp[mask] = 学习 mask 集合所需的最少技能点数
15
    std::vector<int> dp(1 << n, INT_MAX / 2);
16
    dp[0] = 0;
17

18
    int ans = 0;
19
    for (int mask = 0; mask <= FULL; ++mask) {
20
        if (dp[mask] > totalPoints) continue;
21

22
        // 计算当前 mask 的战斗力
23
        int power = 0;
24
        for (int i = 0; i < n; ++i) {
25
            if (mask & (1 << i)) power += skills[i].power;
26
        }
27
        ans = std::max(ans, power);
28

29
        // 尝试学习下一技能
30
        for (int i = 0; i < n; ++i) {
31
            if (mask & (1 << i)) continue;
32
            // 前置技能都已学会？
33
            if ((mask & skills[i].prerequisites) == skills[i].prerequisites) {
34
                int nextMask = mask | (1 << i);
35
                dp[nextMask] = std::min(dp[nextMask],
36
                    dp[mask] + skills[i].cost);
37
            }
38
        }
39
    }
40
    return ans;
41
}

4.8.3 科技树的最优加点 —— 树形 DP#

1
// 科技树是一棵树，每个节点可以投入多个点数
2
// 每个点数增加固定属性，但有递减收益
3
// 树形 DP：对每个子树，计算"分配 j 个点数"的最优收益
4
struct TechNode {
5
    int  baseGain;    // 每点的基础收益
6
    float decay;      // 递减系数
7
    std::vector<int> children;
8

9
    int gain(int points) const {
10
        float total = 0;
11
        for (int p = 0; p < points; ++p) {
12
            total += baseGain * std::pow(decay, p);
13
        }
14
        return static_cast<int>(total);
15
    }
16
};
17

18
int dfsAllocate(int node, int remainingPoints,
19
                const std::vector<TechNode>& tree,
20
                std::vector<std::vector<int>>& memo) {
21
    if (remainingPoints == 0) return 0;
22
    if (memo[node][remainingPoints] != -1) return memo[node][remainingPoints];
23

24
    // 对当前节点分配 0..remainingPoints 点
25
    int best = 0;
26
    for (int toSelf = 0; toSelf <= remainingPoints; ++toSelf) {
27
        int gain = tree[node].gain(toSelf);
28
        int leftPoints = remainingPoints - toSelf;
29

30
        // 子节点的 DP（简化版：按子树权重分配）
31
        // 实际项目中可能需要对子节点再做 DP 合并
32
        int childGain = 0;
33
        for (int child : tree[node].children) {
34
            childGain = std::max(childGain,
35
                dfsAllocate(child, leftPoints, tree, memo));
36
        }
37
        best = std::max(best, gain + childGain);
38
    }
39

40
    return memo[node][remainingPoints] = best;
41
}

4.8.4 技能冷却窗口内的最大伤害 —— 单调队列优化#

1
// 在接下来 T 秒内，每秒可以释放一个技能（不同技能有不同伤害和冷却）
2
// 限制：相邻两次释放间隔至少为 cdMin
3
// dp[t] = 考虑前 t 秒，最大总伤害
4
// dp[t] = max(dp[t-1], max(dp[t-cd] + skillDamage[t]))
5
// 用单调队列维护窗口内的最大值
6
int maxDamageInWindow(const std::vector<int>& skillDamage,
7
                       int cdMin) {
8
    int T = skillDamage.size();
9
    std::vector<int> dp(T + 1, 0);
10
    std::deque<int> dq;  // 存索引，dp 值单调递减
11

12
    dq.push_back(0);
13

14
    for (int t = 1; t <= T; ++t) {
15
        // 不释放技能
16
        dp[t] = dp[t - 1];
17

18
        // 释放技能（需要等 cdMin 冷却）
19
        if (t >= cdMin) {
20
            // 维护窗口：只保留 t - cdMin 之前的
21
            while (!dq.empty() && dq.front() < t - cdMin) {
22
                dq.pop_front();
23
            }
24

25
            if (!dq.empty()) {
26
                dp[t] = std::max(dp[t],
27
                    dp[dq.front()] + skillDamage[t - 1]);
28
            }
29
        }
30

31
        // 维护单调递减
32
        while (!dq.empty() && dp[dq.back()] <= dp[t]) {
33
            dq.pop_back();
34
        }
35
        dq.push_back(t);
36
    }
37
    return dp[T];
38
}

4.9 30 秒速答#

📋 以下是本章核心知识点的面试速答模板。

Q：区间 DP 的遍历顺序为什么必须按长度递增？

因为 dp[l][r] 依赖所有比它更短的区间（如 dp[l][k] 和 dp[k+1][r]）。按长度递增保证了当计算 dp[l][r] 时，所有更短的区间已经算好。按 l 递增遍历不行——因为 dp[0][5] 会依赖 dp[1][4]，但 dp[1][4] 可能还没算。

Q：什么情况下用状态压缩 DP？

当 n ≤ 20 且问题涉及”元素的选取状态”时——TSP、子集划分、状态覆盖。用 int 的二进制位表示集合，状态总数是 2ⁿ。因为指数增长，n 不能太大。GCC 的 __builtin_popcount 可以快速计算集合大小。

Q：树形 DP 和后序遍历的关系？

树形 DP 天然是后序遍历——因为要处理子树的信息汇聚到当前节点。递归版直接后序，迭代版需要先压左再压右最后处理根。核心是定义清楚向上返回什么信息——是单边最大值（路径和问题），还是两个状态（打家劫舍的偷/不偷）。

Q：单调队列优化 DP 适用于什么场景？

转移方程形如 dp[i] = max/min(dp[j]) + f(i)，且 j 在一个随 i 滑动的窗口内。单调队列可以在 O(1) 内取窗口最值，将 O(nk) 优化到 O(n)。常见信号：跳跃游戏、带冷却的技能释放、滑动窗口内的最优决策。

Q：面试中如何快速判断 DP 类型？

四个问题：1) 状态能否用区间 [l,r] 描述？→ 区间 DP；2) n ≤ 20 且与集合选择相关？→ 状压 DP；3) 数据是树，与子树相关？→ 树形 DP；4) 转移中有滑动窗口最值？→ 单调队列优化。都不是就回 Ch3 看线性 DP 和背包。

4.10 本章习题清单#

1
区间 DP：
2
  □ 5.   最长回文子串 —— 区间 DP 入门
3
  □ 312. 戳气球 —— 逆向思维经典
4
  □ 877. 石子游戏 —— 博弈 + 区间 DP
5
  □ 664. 奇怪的打印机 —— 区间 DP 进阶
6
  □ 546. 移除盒子 —— 三维区间 DP（Hard+）
7

8
状压 DP：
9
  □ 698. 划分为 k 个相等的子集 —— 状压 DP 入门
10
  □ 526. 优美的排列 —— 状压 + 排列
11
  □ 847. 访问所有节点的最短路径 —— 状压 BFS/DP
12
  □ 1494. 并行课程 II —— 子集枚举 + DP
13

14
树形 DP：
15
  □ 124. 二叉树中的最大路径和 —— 树形 DP 经典
16
  □ 337. 打家劫舍 III —— 树上双状态 DP
17
  □ 543. 二叉树的直径 —— 简化版路径和
18

19
DP 优化：
20
  □ 1696. 跳跃游戏 VI —— 单调队列优化 DP

📖 下一章：第五章贪心算法 —— DP 的”反面”，从区间调度到跳跃游戏，从霍夫曼编码到贪心正确性证明。

音乐

音乐

第四章动态规划（进阶）—— 区间DP + 状压DP + 树形DP#

4.1 概念直觉 —— 三类进阶 DP 的共性#

4.2 区间 DP —— 从短到长合并#

核心模板#

戳气球 (LeetCode 312)#

石子游戏 (LeetCode 877)#

奇怪的打印机 (LeetCode 664)#

4.3 状态压缩 DP —— 用 bitmask 表示集合#

旅行商问题 TSP#

划分为 k 个相等的子集 (LeetCode 698)#

并行课程 II (LeetCode 1494)#

4.4 树形 DP —— 后序遍历的信息汇聚#

二叉树中的最大路径和 (LeetCode 124)#

打家劫舍 III (LeetCode 337)#

树的最小支配集 (简介)#

4.5 DP 优化技巧#

滚动数组回顾#

单调队列优化 DP#

斜率优化简介#

4.6 DP 类型识别与选型#

4.7 高频面试题精讲#

题目 1：不同路径 III (LeetCode 980)#

4.8 🎮 游戏实战#

4.8.1 合成系统的最优策略 —— 区间 DP#

4.8.2 技能树解锁规划 —— 状压 DP#

4.8.3 科技树的最优加点 —— 树形 DP#

4.8.4 技能冷却窗口内的最大伤害 —— 单调队列优化#

4.9 30 秒速答#

4.10 本章习题清单#

文章分享

评论区

音乐

目录

音乐

音乐

第四章 动态规划（进阶）—— 区间DP + 状压DP + 树形DP

第四章 动态规划（进阶）—— 区间DP + 状压DP + 树形DP#

4.1 概念直觉 —— 三类进阶 DP 的共性#

4.2 区间 DP —— 从短到长合并#

核心模板#

戳气球 (LeetCode 312)#

石子游戏 (LeetCode 877)#

奇怪的打印机 (LeetCode 664)#

4.3 状态压缩 DP —— 用 bitmask 表示集合#

旅行商问题 TSP#

划分为 k 个相等的子集 (LeetCode 698)#

并行课程 II (LeetCode 1494)#

4.4 树形 DP —— 后序遍历的信息汇聚#

二叉树中的最大路径和 (LeetCode 124)#

打家劫舍 III (LeetCode 337)#

树的最小支配集 (简介)#

4.5 DP 优化技巧#

滚动数组回顾#

单调队列优化 DP#

斜率优化简介#

4.6 DP 类型识别与选型#

4.7 高频面试题精讲#

题目 1：不同路径 III (LeetCode 980)#

4.8 🎮 游戏实战#

4.8.1 合成系统的最优策略 —— 区间 DP#

4.8.2 技能树解锁规划 —— 状压 DP#

4.8.3 科技树的最优加点 —— 树形 DP#

4.8.4 技能冷却窗口内的最大伤害 —— 单调队列优化#

4.9 30 秒速答#

4.10 本章习题清单#

文章分享

评论区

音乐

目录

第四章动态规划（进阶）—— 区间DP + 状压DP + 树形DP

第四章动态规划（进阶）—— 区间DP + 状压DP + 树形DP#