Leetcode416 分割等和子集[DP]

题目描述

file

方法一

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 2:
            return False
    total = sum(nums)
    maxNum = max(nums)
    if total % 2 !=0:
        return False
    
    target = total // 2
    if maxNum > target:
        return False
    
    dp = [[0] * (target + 1) for _ in range(n)]
    for i in range(n):
        dp[i][0] = True
    
    dp[0][nums[0]] = True
    for i in range(1, n):
        num = nums[i]
        for j in range(1, target + 1):
            if j >= num:
                dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num]
            else:
                dp[i][j] = dp[i - 1][j]
    
    return True if(dp[n - 1][target]==1) else False

 

思路

  • 回溯超时
  • DP没想到
    -->file
    太难啦