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

张开发
• 2026/4/19 1:38:18 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【算法日记】Day 19 动态规划专题——状态压缩DP（二）
Abstract#动态规划#状压DP#异或1. 题目题目LeetCode 473. 火柴拼正方形核心思路将每根火柴看作一个物品用二进制状态s表示火柴的使用情况。设边长为len定义dp[s]表示状态s下当前正在拼的边上已使用的长度对len取模的结果。这样dp[s]始终表示当前边的剩余容量。转移时枚举所有未使用的火柴i若dp[s] matchsticks[i] len则可以将 i 放入当前边新状态为s | (1 i)新边长为 (dp[s] matchsticks[i]) % len。最终检查dp[(1 n) - 1] 0表示所有火柴刚好拼满四条边。复杂度时间复杂度O ( n ⋅ 2 n ) O(n·2^n)O(n⋅2n)空间复杂度O ( 2 n ) O(2^n)O(2n)。2. 代码classSolution{public:boolmakesquare(vectorintmatchsticks){inttotalLenaccumulate(matchsticks.begin(),matchsticks.end(),0);if(totalLen%4!0)returnfalse;intlentotalLen/4,nmatchsticks.size();vectorintdp(1(n1),-1);dp[0]0;for(ints1;s(1n);s){for(intk0;kn;k){if((s(1k))0)continue;ints1s~(1k);if(dp[s1]0dp[s1]matchsticks[k]len){dp[s](dp[s1]matchsticks[k])%len;break;}}}returndp[(1n)-1]0;}};3. 心得状态压缩建模火柴数量n 15暗示可以用二进制整数表示火柴的选取状态每一位代表一根火柴是否已被使用。这是处理小规模组合问题的常用技巧。状态转移分析dp[s] 表示在状态 s 下当前正在填充的边上已经放置的火柴总长度模边长后的余数。取模是为了在一条边填满后自动切换到下一条边余数为0时表示该边已满开始新边。这种定义将四边的填充过程简化为单边的循环填充。

更多文章