树形DP经典：1997年CTSC选课问题深度解析

一、问题背景与算法思路

选课问题要求在一棵课程树中选择m门课程（选择子课程必须先选父课程），目标是获得最大学分。这个问题完美展现了树形动态规划与分组背包的结合应用。

二、完整代码实现（带详细注释）

#include <iostream>
#include <vector>
#include <algorithm>
using namespACe std;

const int MAXN = 310;
vector<int> tree[MAXN];  // 课程父子关系树
int credit[MAXN];        // 每门课程的学分
int dp[MAXN][MAXN];      // 动态规划表：dp[u][m]表示以u为根选m门课的最大学分
int n, m;                // 总课程数和需要选择的课程数

// 树形DP核心函数
void dfs(int u) {
    // 遍历所有子课程（先处理子树）
    for(int v : tree[u]) {
        dfs(v);
        // 分组背包过程（必须倒序枚举）
        for(int j = m; j >= 0; j--) {
            // 尝试分配k个名额给子树v
            for(int k = 1; k <= j; k++) {
                dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);
            }
        }
    }
    // 处理当前课程（必须选了当前课程才能选子课程）
    if(u != 0) {  // 虚拟根节点0不需要选
        // 为当前课程预留1个位置
        for(int j = m; j >= 1; j--) {
            dp[u][j] = dp[u][j-1] + credit[u];
        }
    }
}

int main() {
    cin >> n >> m;
    // 构建课程树结构（0为虚拟根节点）
    for(int i = 1; i <= n; i++) {
        int pre;  // 先修课程编号
        cin >> pre >> credit[i];
        tree[pre].push_back(i);
    }
    
    dfs(0);  // 从虚拟根开始动态规划
    cout << dp[0][m] << endl;  // 输出结果
    return 0;
}

三、关键算法要点

1. 虚拟根节点技巧：创建虚拟根节点0统一处理森林结构

2. 树形DP框架：DFS后序遍历确保子问题先求解

3. 分组背包思想：将每个子树视为一个物品组

4. 学分累加规则：选择子课程必须选择父课程

四、常见错误提醒

1. 背包枚举顺序错误（必须倒序）

2. 忘记处理虚拟根节点特殊情况

3. 学分累加时机错误

4. 数组越界问题（特别是m=0时）

五、学习价值

通过本题可以掌握：

• 树形DP的基本框架

• 分组背包的应用技巧

• 虚拟节点的设计思想

• 依赖关系的动态规划处理