Java教程

各种dp分类整理

本文主要是介绍各种dp分类整理,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

各种dp分类整理

数位dp

因为比较重要,单独写一篇

见 这篇

状压dp

某篇学术垃圾 中指出,

我们可以说,所有的dp都会有一个“状压”。只不过普通的dp压缩的比较浅显,而使用二进制的状压dp压的比较复杂,才叫它“状压dp”

所以这里特指“状压dp”为“使用二进制压缩状态的dp”

一般都会有一个很小的数,在十几二十的范围内。看到这样的范围,通常可以想到把一个 \(2\) (或者 \(3\)) 放在底下,让它作为指数,这样一个复杂度 (\(3\) 是枚举子集,是 \(3^n\) 的)

一般可以设 \(f(...,S)\) 表示 xxx,选xxx的集合为 \(S\),的方案数。然后把一个集合映射到一个二进制数之后,就可以用bitmask的形式开一个数组存下来了。

例题:我先去睡觉,明天整

更多dp

会有的会有的

gugugu.jpg

这篇关于各种dp分类整理的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!