【leetcode31】

作者

416. 分割等和子集

  1. class Solution:
  2.     def canPartition(self, nums: List[int]) -> bool:
  3.         if sum(nums)%2!=0:
  4.             return False        #和不为偶数直接排除
  5.         target=sum(nums)//2           #均分
  6.         dp=[0]*(target+1)                 #同上
  8.         for i in nums:
  9.             for j in range(target,i-1,-1):
  10.                 dp[j]=max(dp[j],dp[j-i]+i)    #0.1背包
  11.         #print(dp)
  12.         if dp[target]==target:           #关键判断，价值质量相等
  13.                     return True
  14.         return False

发表评论