【算法日记】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(vector<int>&matchsticks){inttotalLen=accumulate(matchsticks.begin(),matchsticks.end(),0);if(totalLen%4!=0)returnfalse;intlen=totalLen/4,n=matchsticks.size();vector<int>dp(1<<(n+1),-1);dp[0]=0;for(ints=1;s<(1<<n);++s){for(intk=0;k<n;++k){if((s&(1<<k))==0)continue;ints1=s&~(1<<k);if(dp[s1]>=0&&dp[s1]+matchsticks[k]<=len){dp[s]=(dp[s1]+matchsticks[k])%len;break;}}}returndp[(1<<n)-1]==0;}};

3. 心得

• 状态压缩建模：火柴数量n <= 15，暗示可以用二进制整数表示火柴的选取状态，每一位代表一根火柴是否已被使用。这是处理小规模组合问题的常用技巧。

• 状态转移分析：dp[s] 表示在状态 s 下，当前正在填充的边上已经放置的火柴总长度模边长后的余数。取模是为了在一条边填满后自动切换到下一条边（余数为0时表示该边已满，开始新边）。这种定义将四边的填充过程简化为单边的循环填充。