刷题记录:416. 分割等和子集

刷题记录:416. 分割等和子集,第1张

题记录:416. 分割等和子集

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]

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5714830.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存