Java教程

状态压缩DP

本文主要是介绍状态压缩DP，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

状态压缩DP

对于某些动态规划问题，可以用深搜来枚举状态，但是那样的话时间复杂度就太高了。对于此类问题我们采用二进制表示状态，用1和0来表示某位置不同的状态。
1、对于状压DP问题，我们一般取一个初始状态。确定状态数组的含义。
2、明确相邻状态的转移,一般我们可以记录某个状态可以转移的相邻状态(打表)。
3、然后从第一行(列)枚举到最后行(列)[视具体情况而定]，根据符合条件的相邻之间的状态转移,由前面推出后面(往往最后才是最终答案)。

下面是做得几道题：

AcWing327玉米田

AcWing291.蒙德里安的梦想

AcWing 1064. 小国王

这篇关于状态压缩DP的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航