# A square joining togetherclassSolution(object):defremoveoneside(self,nums,side):n=len(nums)res=[[0forjinrange(side+1)]foriinrange(n+1)]# res[i][j] = max(res[i - 1][j],res[i-1][j-nums[i-1]]+nums[i-1])foriinrange(1,n+1):forjinrange(1,side+1):res[i][j]=res[i-1][j]# copy the last lineifj>=nums[i-1]and(res[i-1][j-nums[i-1]]+nums[i-1])>res[i-1][j]:# greater thanres[i][j]=res[i-1][j-nums[i-1]]+nums[i-1]ifres[i][j]==side:# the first side appears, then stopwhilei>=1andj>=0:# if greater than, remove item from nums list, if not, move to upper lineifj>=nums[i-1]and(res[i-1][j-nums[i-1]]+nums[i-1])>res[i-1][j]:j-=nums[i-1]nums.remove(nums[i-1])i-=1breakelse:continuebreak# Jump out of the multilayer circulationreturnnumsdefsquare(self,lister):lister=sorted(lister)[::-1]total=sum(lister)iftotal%4!=0:return"No"else:foriinrange(4):self.removeoneside(lister,total/4)# remove 4 sidesiflister==[]:return"Yes"else:return"No"if__name__=="__main__":lister=[1,1,1,1,4]answer=Solution()printanswer.square(lister)
近期评论