1.题目基本信息

1.1.题目描述

你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。

如果你能使这个正方形，则返回 true ，否则返回 false 。

1.2.题目地址

https://leetcode.cn/problems/matchsticks-to-square/description/

2.解题方法

2.1.解题思路

动态规划-状压dp

2.2.解题步骤

第一步，预处理。如果总长不是4的倍数，则可以直接排除

第二步，状态定义。s表示已经取用的火柴的二进制状态；如果dp[s]=-1，表示没法在保证一条边没填满前不能填另一条边的情况下，将火柴放到正方形中；否则dp[s]表示在保证一条边没填满前不能填另一条边的情况下，最短边长对avgLen的取余（优先取填了的边）

第三步，状态初始化。如果一条边都没填，则最短边长为0

第四步，状态转移。dp[s]=next([(dp[s1]+matchsticks[i])%avgLen for i in range(n) if dp[s1]>=0 and dp[s1]+matchsticks[i]>=avgLen])（s1=s&(1<=0为了保证前置状态的有效，dp[s1]+matchsticks[i]>=avgLen保证火柴不被折断）

第五步，如果最终dp[-1]==0表示存在状态转移使n条边都合法的填进四条边

3.解题代码

python3代码

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        # 思路：动态规划-状压dp
        n = len(matchsticks)
        # 第一步，预处理。如果总长不是4的倍数，则可以直接排除
        totalLen = sum(matchsticks)
        if totalLen % 4 != 0:
            return False
        avgLen = totalLen // 4
        # 第二步，状态定义。s表示已经取用的火柴的二进制状态；如果dp[s]=-1，表示没法在保证一条边没填满前不能填另一条边的情况下，将火柴放到正方形中；否则dp[s]表示在保证一条边没填满前不能填另一条边的情况下，最短边长对avgLen的取余（优先取填了的边）
        dp = [-1] * (1 << n)
        # 第三步，状态初始化。如果一条边都没填，则最短边长为0
        dp[0] = 0
        # 第四步，状态转移。dp[s]=next([(dp[s1]+matchsticks[i])%avgLen for i in range(n) if dp[s1]>=0 and dp[s1]+matchsticks[i]>=avgLen])（s1=s&(1<<i)表示s在遍历i时前置状态）（dp[s1]>=0为了保证前置状态的有效，dp[s1]+matchsticks[i]>=avgLen保证火柴不被折断）
        for s in range(1, 1 << n):
            for i in range(n):
                if s & (1 << i):
                    s1 = s & ~(1 << i)
                    if dp[s1] >= 0 and dp[s1] + matchsticks[i] <= avgLen:
                        dp[s] = (dp[s1] + matchsticks[i]) % avgLen
                        break
        # 第五步，如果最终dp[-1]==0表示存在状态转移使n条边都合法的填进四条边
        return dp[(1 << n) - 1] == 0

4.执行结果