【算法日记】Day 18 动态规划专题——状态压缩DP（一）

张开发
• 2026/4/18 10:18:22 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【算法日记】Day 18 动态规划专题——状态压缩DP（一）
Abstract#动态规划#博弈论#状压DP#异或1. 题目题目LeetCode 464. 我能赢吗核心思路使用状态压缩表示哪些数字已被选status的二进制位递归判断当前玩家是否必胜。若剩余目标rest ≤ 0则当前玩家输上一步已获胜。对于当前状态遍历所有可选数字若存在一种选择使得对手必败则当前必胜。记忆化避免重复计算。特判desiredTotal为0时先手胜所有数字总和小于desiredTotal时无人能胜按照题意判先手负。复杂度时间复杂度O ( 2 n ∗ n ) O(2^n * n)O(2n∗n)空间复杂度O ( 2 n ) O(2^n)O(2n)。2. 代码classSolution{public:boolf(intn,intrest,intstatus,vectorintdp){if(rest0)returnfalse;if(dp[status]!0){returndp[status]1;}boolansfalse;for(inti1;in;i){if((status(1i))!0!f(n,rest-i,status^(1i),dp)){anstrue;break;}}dp[status]ans?1:-1;returnans;}boolcanIWin(intmaxChoosableInteger,intdesiredTotal){if(desiredTotal0)returntrue;if(maxChoosableInteger*(maxChoosableInteger1)/2desiredTotal)returnfalse;vectorintdp(1(maxChoosableInteger1),0);returnf(maxChoosableInteger,desiredTotal,(1(maxChoosableInteger1))-1,dp);}};3. 心得动态规划里的状态压缩是什么设计一个整形可变参数status利用status的位信息来表示某个样本是否未被尝试过据此来进行搜索。什么时候可以用动态规划的状态压缩容易知道k个样本下可变参数status的范围是[ 0 , 2 k − 1 ] [0,2^k-1][0,2k−1]并且状态数量会随着样本数量的线性增长而呈指数级增长所以状态DP能解决的问题往往样本数量在20个以内。如果状态压缩失效怎么办如果样本数量非常大以至于状态压缩DP甚至任何DP都失效了那么可以考虑双向广搜明天将会见识一下。参数空间的压缩按理来说本题有两个可变参数——状态status和剩余累加和rest但是注意到status确定则rest随之确定反之则不然所以我们只对status做了DP缓存表。事实上对任意动态规划我们都可以做类似的参数空间分析只关注最关键的可变参数被决定的可变参数在递归中不用管。4. 相关题目LeetCode 52. N皇后 II

更多文章