本文不包含所有类型DP,仅包含我所学
若二维DP超空间,将第一维改成2,每个包含I的地方整体(打括号)&1计算
01背包
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
01背包求方案数
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
完全背包
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
多重背包
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
跳跃DP(LIS)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
区间DP
二进制枚举
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
状态压缩DP
这个比较难,我简单喵两句
状态压缩dp,基于二进制枚举实现,它本质其实是模拟简化了全排列DFS枚举,解决非连续的问题,
比如最小异或值问题:
解法:记已排列CNT个数,通过全排列数组B,用全排列的最后一个结果与数组A的第CNT位进行异或
比如吃奶酪问题:
解法:记吃了第I个奶酪时二进制状态第I位为1,枚举为0的地方,同时开二维记录上一个奶酪位置
它们的共同点是通过枚举二进制状态的每一位,第i位为1表示第i个数被选过