动态规划核心代码模板汇总（CSP-J / CSP-S 考场速查）

本讲汇总了信息学竞赛（CSP-J / CSP-S / NOIP）中最常考的 7 类动态规划标准 C++ 实现模板，方便同学们在刷题与考前集中背诵和复盘。

1. 0-1 背包与完全背包一维滚动模板

核心区别在于容量循环方向：0-1 背包逆序枚举容量（防止同一物品被重复选），完全背包正序枚举容量（允许同一物品选无限次）。

// 0-1 背包：n 个物品，背包容量 m
for (int i = 1; i <= n; i++) {
    for (int j = m; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

// 完全背包：每种物品可选无限次
for (int i = 1; i <= n; i++) {
    for (int j = w[i]; j <= m; j++) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

2. 多重背包（二进制拆分优化模板）

将数量为 c 的同种物品拆分为 1, 2, 4, ..., 2^k, 余数 组合成若干件独立的 0-1 背包物品，时间复杂度从 O(N*M*C) 降至 O(N*M*logC)：

vector<pair<int, long long>> items; // {weight, value}
for (int i = 1; i <= n; i++) {
    int cnt = s[i];
    for (int k = 1; k <= cnt; k <<= 1) {
        items.push_back({k * w[i], 1LL * k * v[i]});
        cnt -= k;
    }
    if (cnt > 0) items.push_back({cnt * w[i], 1LL * cnt * v[i]});
}
for (auto &it : items) {
    for (int j = m; j >= it.first; j--) {
        dp[j] = max(dp[j], dp[j - it.first] + it.second);
    }
}

3. 区间 DP 标准区间枚举模板

先从小到大枚举区间长度 len，再枚举左端点 l，计算出右端点 r = l + len - 1，最后枚举分割点 k：

memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; i++) dp[i][i] = 0;

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] + sum[r] - sum[l - 1]);
        }
    }
}

4. 树形 DP（树上背包与子树汇总模板）

先递归处理所有子节点 v，再利用子树结果更新当前节点 u。若做树上背包，注意利用当前已合并子树大小 sz[u] 进行上下界剪枝，保证整体复杂度严格 O(N*M)：

void dfs(int u, int fa) {
    sz[u] = 1;
    dp[u][1] = val[u];
    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs(v, u);
        for (int j = min(m, sz[u] + sz[v]); j >= 1; j--) {
            for (int k = max(1, j - sz[u]); k <= min(j - 1, sz[v]); k++) {
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
            }
        }
        sz[u] += sz[v];
    }
}

5. 状态压缩 DP（子集与状态转移模板）

// 枚举所有状态 mask，以及枚举 mask 的所有非空子集 sub
for (int mask = 0; mask < (1 << n); mask++) {
    for (int sub = mask; sub; sub = (sub - 1) & mask) {
        dp[mask] = min(dp[mask], dp[mask ^ sub] + cost[sub]);
    }
}

6. 数位 DP（记忆化搜索通用模板）

long long memo[20][200];
int a[20], len;

long long dfs(int pos, int state, bool lead, bool limit) {
    if (pos == 0) return 1;
    if (!limit && !lead && memo[pos][state] != -1) return memo[pos][state];
    int up = limit ? a[pos] : 9;
    long long res = 0;
    for (int d = 0; d <= up; d++) {
        res += dfs(pos - 1, state + d, lead && (d == 0), limit && (d == up));
    }
    if (!limit && !lead) memo[pos][state] = res;
    return res;
}

7. 单调队列优化 DP（滑动窗口最值转移模板）

deque<int> q;
q.push_back(0);
for (int i = 1; i <= n; i++) {
    while (!q.empty() && q.front() < i - k) q.pop_front();
    dp[i] = dp[q.front()] + a[i];
    while (!q.empty() && dp[q.back()] <= dp[i]) q.pop_back();
    q.push_back(i);
}