1、背包DP
01
01
f
[
j
]
=
m
a
x
(
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)
- 多重背包(物品有
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)
s
s
01
01
- 混合背包(前三种混合体):有限个物品则用多重背包方式优化做,无限物品则完全背包做。
- 分组背包(每个组只能选1个):一维方法:先枚举体积后枚举物品,且体积枚举从大到小同时需要枚举到0。二维方法先枚举物品再枚举体积,体积也从大枚举到小需要枚举到0.
- 依赖背包(树形背包):状态定义
f
[
u
]
[
i
]
f[u][i]
u
u
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
]
[
i
]
f[u][i]
j
j
[
V
,
w
e
i
[
u
]
+
w
e
i
[
v
]
]
[V,wei[u]+wei[v]]
[
w
e
i
[
v
]
,
u
−
w
e
i
[
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]
- 走的方块数量限制:曼哈顿距离
(
1
,
1
)
−
>
(
n
,
n
)
(1,1)->(n,n)
2
n
−
2
2n-2
- 走两条路:状态定义
f
[
k
]
[
i
]
[
j
]
f[k][i][j]
k
k
x
1
=
i
x_1=i
x
2
=
j
x_2=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 \}
- 两条路径不能交叉,实际证明按上面的方式做就可以,上面的最优情况是可以变成不经过重复路线。
- 朴素版:只能从上走下来和从左边走过来
- 最长上升子序列模型
- 最长公共子序列:
O
(
n
2
)
O(n^2)
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])
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)
- 最长公共子串:
O
(
n
2
)
O(n^2)
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])
- 最长上升子序列:
- 方式1:
O
(
n
2
)
O(n^2)
f
[
i
]
f[i]
i
i
j
∈
[
1
,
i
)
j \in[1,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)
- 方式2:
O
(
n
l
o
g
n
)
O(nlogn)
a
[
i
]
>
s
[
−
1
]
a[i]>s[-1]
a
[
i
]
a[i]
s
s
s
s
a
[
i
]
a[i]
a
[
i
]
a[i]
- 方式1:
- 最长公共子序列:
3、状压DP
- TSP问题:定义状态
f
[
i
]
[
j
]
f[i][j]
i
i
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])
i
i
i
′
i’
i
′
i’
i
i
i
′
i’
k
k
k
k
j
j
O
(
n
2
∗
2
n
)
O(n^2*2^n)
n
n
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]
u
u
i
f
f
[
v
]
>
0
:
f
[
u
]
+
=
f
[
v
]
if \ f[v]>0:f[u]+=f[v]
- 求树的直径:第一次从根节点
d
f
s
dfs
s
s
s
s
p
p
s
s
p
p
- 树型
D
P
DP