ALGORITHM NOTES阅读地图
7个主要章节
2段代码示例
9组图片与图表

先明确状态与不变量，再对照手算、证明、边界和实现。

章节速览7 节 · 展开选择

写动态规划时，最容易卡住的地方往往不是循环，而是这句话：dp[i] 究竟表示什么？如果状态只写成“到 i 的最优解”，那么“恰好到达”和“不超过 i”就可能混在一起，初始化也会跟着出错。

本文用两道题练习两个不同的状态轴：一题按已使用的长度递推，另一题按数值大小递推。建议先独立画出状态表，再看代码。

1. 两道题，两个关键问题

题目 官方难度 官方标签 本文训练重点
189A · Cut Ribbon 1300 brute force、dp 恰好填满与不可达状态
455A · Boredom 1500 dp 按值聚合与相邻冲突

名称、难度和标签于 2026-09-05 通过 Codeforces 官方 API 核对。下文是原创建模与解法说明，不是题面翻译；所有推演表均使用自拟例子。

读过 贪心三题 后，可以把这篇当作下一步：当一个局部选择无法保证未来仍然最优时，保留不同状态的最优结果，之后再比较。

2. Cut Ribbon：为什么不能一直选最短的一段

给定总长度 n，每段只能取 a、b、c 三种正整数长度，目标是在不剩余材料的前提下，让段数最多。题目保证有解，四个输入数均不超过 4000。

先看反例：总长度为 7，允许长度为 2、3、5。连续取最短的 2，会留下无法处理的 1；合法最优方案却是 2 + 2 + 3，共 3 段。

“短段更有利”只是方向感。能否恰好填满剩余长度，必须进入状态。

定义状态与初始化

定义 dp[len] 为：恰好拼出长度 len 时，最多可以使用多少段。

  • dp[0] = 0：空方案恰好拼出 0，使用 0 段。
  • 其余位置初始化为 -1：暂时没有合法方案。
  • 因为合法段数必定非负，这里的 -1 可以明确代表不可达。

不能把整个数组初始化为 0。例如允许长度 2、3、5 时，长度 1 不可达，不能在这个“假方案”后再接一段。

从最后一段反推转移

假设最后一段长度为 piece，去掉它后，前面的段必须恰好拼出 len - piece。只有前驱可达时，才考虑候选值 dp[len - piece] + 1。

仍用 n=7，长度集合={2,3,5} 手算：

len 0 1 2 3 4 5 6 7
dp[len] 0 不可达 1 1 2 2 3 3
一种最优拆法 空 — 2 3 2+2 2+3 2+2+2 2+2+3

注意长度 5 可以直接取一段 5，也可以拆成两段 2 和 3；状态保存的是“最多段数”，因此取 2。

C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, a, b, c;
    cin >> n >> a >> b >> c;
    vector<int> dp(n + 1, -1);
    dp[0] = 0;
    for (int len = 1; len <= n; ++len) {
        for (int piece : {a, b, c}) {
            if (len >= piece && dp[len - piece] != -1) {
                dp[len] = max(dp[len], dp[len - piece] + 1);
            }
        }
    }
    cout << dp[n] << '\n';
}

为什么这个转移不会漏掉最优解

任何合法方案都有最后一段，它必然属于三种允许长度之一。去掉最后一段后，如果剩余方案不是对应前驱的最优方案，就可以替换成更优方案，使总段数进一步增加。因此，只需比较三种最后一段所对应的最优前驱。

所有长度为正，前驱下标一定小于当前下标；从小到大计算时，依赖都已完成。每个长度只检查三次，时间为 O(n)，空间为 O(n)。允许长度重复也不影响答案，只会重复检查同一候选。

3. Boredom：状态轴为什么不是数组下标

每次选一个数值 x 获得 x 分，并删除所有值为 x-1 和 x+1 的元素。相同数值的其他元素仍然存在。输入最多有十万个数，每个值介于 1 和十万之间。

冲突取决于数值相差一，与两个元素在原数组里是否挨着无关。因此，应该先统计 count[x]，把每个值的总收益记为 gain[x] = x * count[x]。

一旦决定选择值 x，它的所有副本都可以依次选走：继续选同值不会引入新的冲突，而且收益为正。原问题就变成：从数轴上选择一些互不相邻的位置，让总权重最大。

收益最大的值也不能盲目先拿

考虑数组 [2, 2, 3, 3, 3, 4, 4]。各值的总收益为 4、9、8。优先拿收益最大的 3，只能得到 9；选择 2 和 4 则能得到 12。

局部最大收益会同时排斥左右两侧，失去的机会可能更大。

定义状态，拆成互斥的两类

令 dp[v] 表示：只允许使用数值 1…v 时，最多能得多少分。

对值 v 的选择 前面还能选择的范围 候选收益
不选 v 1…v-1 dp[v-1]
选择所有 v 1…v-2 dp[v-2] + gain[v]

所以 dp[v] = max(dp[v-1], dp[v-2] + gain[v])，边界为 dp[0]=0、dp[1]=gain[1]。

用上面的例子逐步计算：

v gain[v] 跳过 v 选择 v dp[v]
1 0 0 0 0
2 4 0 4 4
3 9 4 9 9
4 8 9 4+8 12

这里的 0 不是“不可达”。即使一个值都不选，也能合法得到 0 分；它与上一题的初始化语义完全不同。

C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> gain(100001, 0);
    int maximum = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        gain[x] += x;
        maximum = max(maximum, x);
    }

    vector<long long> dp(maximum + 1, 0);
    dp[1] = gain[1];  // 题目保证至少一个数，且所有数为正
    for (int v = 2; v <= maximum; ++v) {
        dp[v] = max(dp[v - 1], dp[v - 2] + gain[v]);
    }
    cout << dp[maximum] << '\n';
}

每个最优方案要么不选 v，要么选择 v 并排除 v-1；两类互斥且覆盖所有方案。对两个前驱应用同样结论，就得到归纳证明。

设值域上限为 V=100000，统计和初始化加递推的时间为 O(n+V)，空间为 O(V)。总收益可能达到 10^10，必须使用 long long。后续可以用两个变量压缩 DP 数组，但先保留完整状态更利于调试。

4. 把状态写成一句能被检查的话

检查项 Cut Ribbon Boredom
状态轴 已拼出的精确长度 允许使用的数值上界
最后一个决策 最后一段取哪种长度 当前值选还是不选
空方案是否合法 仅长度 0 合法 任意前缀均可不选
不可达如何表示 -1，且必须检查前驱 不需要单独标记
计算顺序 长度从小到大 数值从小到大

遇到新题时，先补全“在什么限制下，记录什么最优值”。然后检查不同历史是否真的能合并：如果未来还依赖一个没有记录的条件，当前状态就不够用。

5. 自测与继续练习

可以用下面几组输入主动检查边界：

  • Cut Ribbon：1 1 1 1 应得 1；7 2 3 5 应得 3；7 2 4 7 应得 1，检查算法是否错误接受剩余长度。
  • Boredom：只有一个 7，应得 7；[1,1,2,2,3,3] 应得 8；十万个 100000 应得 10000000000，检查溢出。

更可靠的本地方法是小规模对拍：剪绳题枚举三种段的数量；删数题枚举不同数值的所有子集，排除包含相邻数值的子集，再与 DP 比较。这样的穷举检查与快速算法采用不同思路，更容易发现共同样例之外的问题。

6. 从最优值还原一组方案

“答案是 3 段”与“具体怎样切”是两个不同的输出要求。可以在每次严格改善 dp[len] 时，同时记录 last[len]=piece；回溯时从 len=n 开始，不断取出 last[len] 并令 len-=last[len]。

仍取长度 7、允许段长 {2,3,5}，按 2、3、5 的顺序检查，只在候选值严格更大时更新，可得到下面一条回溯链：

当前长度 记录的最后一段 前驱长度 校验
7 2 5 dp[7]=dp[5]+1=3
5 2 3 dp[5]=dp[3]+1=2
3 3 0 dp[3]=dp[0]+1=1

读出的段长为 2、2、3，总长度为 7、段数为 3。它是从后往前取出的；本题切段顺序不影响合法性，如果是需要按发生顺序输出的路径题，应将回溯结果反转。

有三个实现细节值得主动检查：

  • last 必须与改善后的最优值一起更新，不能在每次枚举候选时无条件覆盖。
  • 候选并列最优时保留任意一个即可，只能保证得到一组方案，不保证字典序最小或列出所有方案。
  • 仅从可达目标开始回溯；每条记录的段长为正，因此长度严格减小，最终到达 0，不会形成环。

Boredom 也可还原：从最大数值 v 向左走，若 dp[v]==dp[v-1]，可以跳过 v；否则选中所有 v，并跨过冲突值退到 v-2。到 v=1 时单独处理边界。上面的收益 4、9、8 例子会选中 4，再选中 2，得到 12。

这解释了为何初学时值得保留完整 DP 数组：两个滚动变量能算最优值，但不足以直接进行这类回溯。压缩空间前，先问清楚是否还需要输出具体方案。

7. 改成计数，不能只把 max 换成加号

目标 空状态 候选的合并方式 还要确认什么
最多切多少段 0 段 取最大值 不可达前驱不能参与
有多少种有序拼法 1 个空方案 将互斥来源相加 最后一段能否唯一分类
有多少种无序组合 1 个空方案 在固定枚举规则下累加 如何避免排列被重复计算

还有一个容易忽略的变化：当 a=b 时，重复枚举对最大值没有影响；如果改为计数，且相同长度不区分来源，就必须先去重，否则会把同一种切法重复计数。

可以接着读 474D Flowers：计数 DP 与前缀和，观察“顺序算不同”如何决定递推；再读 520B：状态图与 BFS，比较有序依赖和带环状态图的处理方式。

回到 算法练习路径 可以对照贪心和二分；如果对 AI 中“多找几个候选再验证”感兴趣，可以继续读 大模型推理时计算，比较精确算法证明与统计验证的差别。