1、背包DP
01
01
01背包：枚举物品然后枚举体积，体积从大到小枚举更新f
[
j
]
=
m
a
x
(
f
[
j
]
,
f
[
j
−
w
]
+
v
)
f[j]=max(f[j],f[j-w]+v)
f[j]=max(f[j],f[j−w]+v).- 完全背包：枚举物品然后枚举体积，体积从小到大枚举更新
f
[
j
]
=
m
a
x
(
f
[
j
]
,
f
[
j
−
w
]
+
v
)
f[j]=max(f[j],f[j-w]+v)
f[j]=max(f[j],f[j−w]+v). - 多重背包(物品有
k
k
k个)：枚举物品后，二进制方式枚举物品件数。体积从大到小枚举，更新：f
[
j
]
=
m
a
x
(
f
[
j
]
,
f
[
j
−
k
∗
w
]
+
k
∗
v
)
f[j]=max(f[j],f[j-k*w]+k*v)
f[j]=max(f[j],f[j−k∗w]+k∗v).最后判断剩余s
s
s是否大于0，如果大于0再做一遍01
01
01背包。 - 混合背包(前三种混合体)：有限个物品则用多重背包方式优化做，无限物品则完全背包做。
- 分组背包(每个组只能选1个)：一维方法：先枚举体积后枚举物品，且体积枚举从大到小同时需要枚举到0。二维方法先枚举物品再枚举体积，体积也从大枚举到小需要枚举到0.
- 依赖背包(树形背包)：状态定义
f
[
u
]
[
i
]
f[u][i]
f[u][i]以u
u
u为根节点的子树中i
i
i体积最多可以获得的价值，需要通过回溯再继续更新f
[
u
]
[
j
]
=
m
a
x
(
f
[
u
]
[
j
]
,
f
[
u
]
[
j
−
k
]
+
f
[
v
]
[
k
]
)
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k])
f[u][j]=max(f[u][j],f[u][j−k]+f[v][k]).每次递归需要预处理出f
[
u
]
[
i
]
f[u][i]
f[u][i]的值。更新先枚举总体积j
j
j从大到小枚举[
V
,
w
e
i
[
u
]
+
w
e
i
[
v
]
]
[V,wei[u]+wei[v]]
[V,wei[u]+wei[v]].然后枚举分配到子节点的体积[
w
e
i
[
v
]
,
u
−
w
e
i
[
u
]
]
[wei[v],u-wei[u]]
[wei[v],u−wei[u]].
2、线性DP
- 数字三角形模型
- 朴素版：只能从上走下来和从左边走过来
f
[
i
]
[
j
]
=
m
a
x
(
f
[
i
]
[
j
−
1
]
,
f
[
i
−
1
]
[
j
]
)
+
w
[
i
]
[
j
]
f[i][j]=max(f[i][j-1],f[i-1][j])+w[i][j]
f[i][j]=max(f[i][j−1],f[i−1][j])+w[i][j]. - 走的方块数量限制：曼哈顿距离
(
1
,
1
)
−
>
(
n
,
n
)
(1,1)->(n,n)
(1,1)−>(n,n)为2
n
−
2
2n-2
2n−2.所以考虑是不是走的最短路 - 走两条路：状态定义
f
[
k
]
[
i
]
[
j
]
f[k][i][j]
f[k][i][j]表示路径的长度为k
k
k，第一条路径到达x
1
=
i
x_1=i
x1=i，第二条路径到达x
2
=
j
x_2=j
x2=j的方案数。因此状态转移：f
k
,
i
,
j
=
m
a
x
{
f
k
−
1
,
i
,
j
,
f
k
−
1
,
i
−
1
,
j
,
f
k
−
1
,
i
,
j
−
1
,
f
k
−
1
,
i
−
1
,
j
−
1
+
w
}
f_{k,i,j}=max\{ f_{k-1,i,j},f_{k-1,i-1,j},f_{k-1,i,j-1},f_{k-1,i-1,j-1}+w \}
fk,i,j=max{fk−1,i,j,fk−1,i−1,j,fk−1,i,j−1,fk−1,i−1,j−1+w} - 两条路径不能交叉，实际证明按上面的方式做就可以，上面的最优情况是可以变成不经过重复路线。
- 朴素版：只能从上走下来和从左边走过来
- 最长上升子序列模型
- 最长公共子序列：
O
(
n
2
)
O(n^2)
O(n2)，方程：f
[
i
]
[
j
]
=
m
a
x
(
f
[
i
−
1
]
[
j
]
,
f
[
i
]
[
j
−
1
]
)
f[i][j]=max(f[i-1][j],f[i][j-1])
f[i][j]=max(f[i−1][j],f[i][j−1])，如果a
[
i
]
=
=
b
[
i
]
,
f
[
i
]
[
j
]
=
m
a
x
(
f
[
i
]
[
j
]
,
f
[
i
−
1
]
[
j
−
1
]
+
1
)
a[i]==b[i],f[i][j]=max(f[i][j],f[i-1][j-1]+1)
a[i]==b[i],f[i][j]=max(f[i][j],f[i−1][j−1]+1) - 最长公共子串：
O
(
n
2
)
O(n^2)
O(n2)，方程：f
[
i
]
[
j
]
=
m
a
x
(
f
[
i
]
[
j
]
,
f
[
i
−
1
]
[
j
−
1
]
)
f[i][j]=max(f[i][j],f[i-1][j-1])
f[i][j]=max(f[i][j],f[i−1][j−1]). - 最长上升子序列：
- 方式1：
O
(
n
2
)
O(n^2)
O(n2)，状态f
[
i
]
f[i]
f[i]表示前i
i
i个数的最长上升子序列长度，更新：从j
∈
[
1
,
i
)
j \in[1,i)
j∈[1,i)找到每一个a
[
j
]
<
=
a
[
i
]
a[j]<=a[i]
a[j]<=a[i]更新f
[
i
]
=
m
a
x
(
f
[
i
]
,
f
[
j
]
+
1
)
f[i]=max(f[i],f[j]+1)
f[i]=max(f[i],f[j]+1). - 方式2：
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)，用一个列表存储一个上升子序列，当a
[
i
]
>
s
[
−
1
]
a[i]>s[-1]
a[i]>s[−1]时将a
[
i
]
a[i]
a[i]加入到s
s
s中，小于时，二分查找s
s
s列表找到第一个大于等于a
[
i
]
a[i]
a[i]的值用a
[
i
]
a[i]
a[i]替换掉。
- 方式1：
- 最长公共子序列：
3、状压DP
- TSP问题：定义状态
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示当前已近到达的状态为i
i
i，最后到达的城市是j
j
j，基本的状态转移方程为：f
[
i
]
[
j
]
=
m
i
n
(
f
[
i
]
[
j
]
,
f
[
i
′
]
[
k
]
+
d
[
j
]
[
k
]
)
f[i][j] = min(f[i][j],f[i’][k]+d[j][k])
f[i][j]=min(f[i][j],f[i′][k]+d[j][k])，基于当前的状态i
i
i枚举前一个状态i
′
i’
i′，每次尝试更新从i
′
i’
i′到i
i
i，其中i
′
i’
i′状态最后到达的是k
k
k节点，然后更新是从k
k
k走到j
j
j。时间复杂度O
(
n
2
∗
2
n
)
O(n^2*2^n)
O(n2∗2n)这里的n
n
n的大小一般小于等于18
18
18. - 状压一般就是枚举两个状态，当前状态和能够影响当前状态的前一状态，通过前一状态转移到当前状态。状态之间的转移一般比较容易。
4、数位DP
数位
D
P
DP
DP基本可以套板子，主要问题就是考虑前导0是否影响答案，也就是考虑
023
023
023和
23
23
23的区别有没有。下面是通用的板子。其他参数只有
t
o
t
a
l
total
total是需要被考虑的。
i
s
_
l
i
m
i
t
is\_limit
is_limit表示的是达到了上线的数字。
i
s
_
n
u
m
is\_num
is_num是表示是否是非0的数字
from functools import lru_cache @lru_cache(maxsize=None) l,r = map(int,input().split()) def f(s,i,total,is_limit,is_num,res=0): if i==len(s): return total #是否符合条件 # 如果023和23有区别则需要处理前导0 if not is_num:res += f(s,i+1,0,False,False) up = int(s[i]) if is_limit else 9 for d in range(1-int(is_num),up+1): res += f(s,i+1,total+某个值,is_limit and d==up,True) return res print(f(str(r),0,0,True,False)-f(str(l-1),0,0,True,False)) # 如果计算f(r)和f(l-1)时会有关联可以计算一个后清空cache f.cache_clear()
5、树型DP
- 求树的最大权值：类似于求最大子段和，只不过在树上，每次递归的时候先初始化
f
[
u
]
=
a
[
u
]
f[u]=a[u]
f[u]=a[u]，然后递归u
u
u节点的每一个子节点，回溯的时候进行更新i
f
f
[
v
]
>
0
:
f
[
u
]
+
=
f
[
v
]
if \ f[v]>0:f[u]+=f[v]
if f[v]>0:f[u]+=f[v] - 求树的直径：第一次从根节点
d
f
s
dfs
dfs递归到一个深度最大的节点s
s
s，然后以s
s
s以根节点递归都得一个最大深度的节点p
p
p，那么节点s
s
s到p
p
p就是树的直径。递归每个节点的儿子节点时遇到父节点跳过。 - 树型
D
P
DP
DP的基本思路是递归的开始进行预处理，然后枚举根节点的每个儿子节点，对儿子节点进行递归，回溯的时候再进行更新。
