shout out to professor Adzlpxsn.
upd at oct 16th 2025, 修复了时间复杂度分析的重大失误.
基本的, 状态, 转移, 方程
状态
一句话概况即为当前的属性.
比如说, 贝贝现在是
30
30 岁, 发了
0
0 张专辑, 我们就可以说
�
30
=
0
f
30
=0.
这里我们说
30
30 和
0
0 是不同的信息, 所以一个状态
�
�
=
�
f
x
=y 里包含的信息其实有
�
x 和
�
y.
同样的,
�
�
,
�
=
�
f
x,y
=z 里包含的信息有
3
3 个, 即
�
x
�
y
�
z.
转移
转移, 就是说用
�
�
f
x
推算
�
�
f
y
, 或者用
�
�
f
x
和
�
�
f
y
推算
�
�
f
z
.
举个例子.
贝贝的新专辑 "金手指", 第
�
x 首歌是 boombap 还是 trap 取决于第
�
−
1
x−1 首和第
�
−
2
x−2 首, 即
�
�
=
(
�
�
−
1
+
�
�
−
2
)
m
o
d
2
f
x
=(f
x−1
+f
x−2
)mod2. 那么我们就说
�
�
f
x
由
�
�
−
1
f
x−1
和
�
�
−
2
f
x−2
转移而来.
方程
方程就是把转移的过程写成人类能看懂的东西, 比如 "数学语言" "自然语言" "编程语言".
线性 dp
最简单的线性 dp, 就是跳跃问题.
problem:AtCoder-dp_a
考虑状态, 我们让
�
�
f
x
表示现在位于
�
�
�
�
�
�
stone
x
时最少跳了多少.
转移就比较容易了,
�
�
=
std::min
(
�
�
−
2
+
∣
ℎ
�
−
2
−
ℎ
�
∣
,
�
�
−
1
+
∣
ℎ
�
−
1
−
ℎ
�
∣
)
f
x
=std::min(f
x−2
+∣h
x−2
−h
x
∣,f
x−1
+∣h
x−1
−h
x
∣).
没什么好讲的, 注意边界条件初始化就好了, 难的题就很难.
背包 dp
这个就好玩了.
01 背包
我个人觉得背包 dp 和线性 dp 大抵是有血缘关系的罢.
problem:AtCoder-dp_d
可以想到, 我们让
�
�
f
c
表示在背包容量为
�
c 时的最大价值.
于是有转移方程
�
�
=
std::max
(
�
�
,
�
�
−
�
�
+
�
�
)
f
c
=std::max(f
c
,f
c−w
x
+v
x
).
那么这时候我们有一个问题.
如果内层循环从
�
�
w
x
枚举到
�
W, 那么有可能会造成重复选择, 但题意说每个物品只有
1
1 个.
于是我们可以调转内层循环的方向, 从
�
W 枚举到
�
�
w
x
, 此时每个物品就只会被选一次了.
代码
for(ll x=1;x<=n;x++) // 枚举每个物品
for(ll c=W;w[x]<=c;c--) // 枚举背包大小
f[c]=std::max(f[c],f[c-w[x]]+v[x]); // 转移
std::cout<<f[W]<<"\n";
完全背包
再考虑, 如果每个物品可以选无数次呢?
problem:洛谷-P1616
显然, 只要把内层循环的方向调回去就可以了.
for(ll x=1;x<=n;x++) // 枚举每个物品
for(ll c=w[x];c<=W;c++) // 枚举背包大小
f[c]=std::max(f[c],f[c-w[x]]+v[x]); // 转移
std::cout<<f[W]<<"\n";
多重背包
现在我们说, 每个物品不止有
1
1 个, 但也不能无限选, 于是我们说物品
�
x 有
�
�
t
x
个, 这就是多重背包.
problem:洛谷-1776
如果当成
�
�
t
x
个相同物品那么显然会超时, 因为
∑
�
∈
[
1
,
�
]
�
�
≥
+
∞
x∈[1,n]
∑
t
x
≥+∞.
于是我们想, 我们学计算机最重要的是什么? 是二进制.
是的, 我们只要拆分成二进制就好了.
std::vector<ll>v,w;
for(ll x=1;x<=n;x++){
ll vx,wx,tx;
std::cin>>vx>>wx>>tx;
for(ll f=1;f<=tx;f<<=1){ // 二进制分解
v.emplace_back(vx*f);
w.emplace_back(wx*f);
tx-=f;
} if(tx!=0){ // 最后还剩一点点, 单独做成一个
v.emplace_back(vx*tx);
w.emplace_back(wx*tx);
}
}
然后跑一遍 01 背包就解决了.
分组背包
当每一组物品里只能选
1
1 个的时候应该怎么办呢?
problem:洛谷-P1757
这里留给读者思考, 简单放一下代码, 和 01 背包也差不多.
ll t=0;
std::vector<std::vector<ll>>g(n+1);
for(ll x=1;x<=n;x++){
ll s;
std::cin>>w[x]>>v[x]>>s;
t=std::max(t,s);
g[s].emplace_back(x);
}
for(ll s=1;s<=t;s++)
for(ll c=W;0<=c;c--)
for(ll x:g[s])
if(w[x]<=c)
f[c]=std::max(f[c],f[c-w[x]]+v[x]);
std::cout<<f[W]<<"\n";
时间复杂度总结
像线性 dp 就是
�
(
�
∗
�
)
O(n∗k), 其中
�
k 为转移复杂度, 比如之后会讲的优化就能搞出
�
=
log
�
k=logn.
背包 dp 就比较固定了, 都是
�
(
�
∗
�
)
O(n∗W). 特别的, 由于多重背包是二进制搞来的, 所以多重背包的
�
′
=
∑
�
∈
[
1
,
�
]
log
�
�
n
′
=
x∈[1,n]
∑
logt
x
)
