各种dp分类整理
2021/8/4 23:06:34
本文主要是介绍各种dp分类整理,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
各种dp分类整理
数位dp
因为比较重要,单独写一篇
见 这篇
状压dp
某篇学术垃圾 中指出,
我们可以说,所有的dp都会有一个“状压”。只不过普通的dp压缩的比较浅显,而使用二进制的状压dp压的比较复杂,才叫它“状压dp”
所以这里特指“状压dp”为“使用二进制压缩状态的dp”
一般都会有一个很小的数,在十几二十的范围内。看到这样的范围,通常可以想到把一个 \(2\) (或者 \(3\)) 放在底下,让它作为指数,这样一个复杂度 (\(3\) 是枚举子集,是 \(3^n\) 的)
一般可以设 \(f(...,S)\) 表示 xxx,选xxx的集合为 \(S\),的方案数。然后把一个集合映射到一个二进制数之后,就可以用bitmask的形式开一个数组存下来了。
例题:我先去睡觉,明天整
更多dp
会有的会有的
这篇关于各种dp分类整理的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现