博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
状压dp终极篇(状态转移的思想)
阅读量:4329 次
发布时间:2019-06-06

本文共 368 字,大约阅读时间需要 1 分钟。

状压dp是将每种状态都压缩成用一个二进制串,然后利用位运算进行操作的dp,而凡是dp都需要进行状态转移

对于简单的dp问题只需要一个二维数组dp[ i ][ j ]就能解决

具体操作为首先把状态压缩为二进制串,

然后对第一行进行初始化,

再利用三个for循环进行状态转移(第一层for循环控制行的前进,第二个和第三个for循环控制本行和上一行的状态)

利用状态转移对二维数组进行不断的更新(可以想到其实就是在不断更新填写一个二维表)

而复杂一点的dp问题就需要一个三维数组dp[ i ][ k ][ j ]才能解决

具体操作和二维的一样,只是需要四个循环(多了一个循环遍历更新k了,也就是可以认为是在更新一个三维的表)

 

转载于:https://www.cnblogs.com/MekakuCityActor/p/8538604.html

你可能感兴趣的文章
Blob(二进制)、byte[]、long、date之间的类型转换
查看>>
OO第一次总结博客
查看>>
day7
查看>>
iphone移动端踩坑
查看>>
vs无法加载项目
查看>>
Beanutils基本用法
查看>>
玉伯的一道课后题题解(关于 IEEE 754 双精度浮点型精度损失)
查看>>
《BI那点儿事》数据流转换——百分比抽样、行抽样
查看>>
哈希(1) hash的基本知识回顾
查看>>
Leetcode 6——ZigZag Conversion
查看>>
dockerfile_nginx+PHP+mongo数据库_完美搭建
查看>>
Http协议的学习
查看>>
【转】轻松记住大端小端的含义(附对大端和小端的解释)
查看>>
设计模式那点事读书笔记(3)----建造者模式
查看>>
ActiveMQ学习笔记(1)----初识ActiveMQ
查看>>
Java与算法之(2) - 快速排序
查看>>
Windows之IOCP
查看>>
机器学习降维之主成分分析
查看>>
CTP2交易所成交回报
查看>>
WebSocket & websockets
查看>>