Golang | Leetcode Golang题解之第473题火柴拼正方形
题目:
题解:
func makesquare(matchsticks []int) bool {
totalLen := 0
for _, l := range matchsticks {
totalLen += l
}
if totalLen%4 != 0 {
return false
}
tLen := totalLen / 4
dp := make([]int, 1<<len(matchsticks))
for i := 1; i < len(dp); i++ {
dp[i] = -1
}
for s := 1; s < len(dp); s++ {
for k, v := range matchsticks {
if s>>k&1 == 0 {
continue
}
s1 := s &^ (1 << k)
if dp[s1] >= 0 && dp[s1]+v <= tLen {
dp[s] = (dp[s1] + v) % tLen
break
}
}
}
return dp[len(dp)-1] == 0
}
原文地址:https://blog.csdn.net/weixin_66442839/article/details/142867247
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!