416. 分割等和子集
class Solution: def canPartition(self, nums: List[int]) -> bool: target = sum(nums) / 2 if target != int(target): return False n = len(nums) target = int(target) dp = [[False]*(target + 1) for _ in range(n + 1)] for i in range(n+1): dp[i][0] = True for i in range(1,n+1): for j in range(1,target+1): if j - nums[i-1] >= 0: dp[i][j] = dp[i-1][j] or dp[i-1][j - nums[i-1]] else: dp[i][j] = dp[i-1][j] return dp[-1][-1]
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)