代码随想录 -- 动态规划 -- 分割等和子集

416. 分割等和子集 - 力扣（LeetCode）

思路：

题目中表述：将数组nums分割成两个子集，使得两个子集的元素和相等。

可以转化为：有一个背包，如果存在部分元素组合可以令容量为nums的和的一半的背包容纳的最大价值也为nums的和的一半，那么剩下的元素和也是nums的一半，则符合题意。

• dp[j]含义：容量为j的背包，能容纳的最大价值。
• 递推公式：dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])
• 初始化：都初始化为0
• 遍历顺序：先遍历物品，再遍历背包，从后向前遍历背包，好像遍历物品的顺序不重要？

class Solution(object):
    def canPartition(self, nums):
        if sum(nums)%2!=0:return False
        target=sum(nums)/2
        dp=[0]*(target+1)
        for i in range(len(nums)-1,-1,-1):
            for j in range(target,-1,-1):
                if j-nums[i]>=0:
                    dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])
        if dp[target]==target:return True
        else:return False

class Solution(object):
    def canPartition(self, nums):
        if sum(nums)%2!=0:return False
        target=sum(nums)/2
        dp=[0]*(target+1)
        for i in range(len(nums)):
            for j in range(target,-1,-1):
                if j-nums[i]>=0:
                    dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])
        if dp[target]==target:return True
        else:return False

题解：对背包的遍历从target到nums[i]-1.

class Solution(object):
    def canPartition(self, nums):
        if sum(nums)%2!=0:return False
        target=sum(nums)/2
        dp=[0]*(target+1)
        for i in range(len(nums)):
            for j in range(target,nums[i]-1,-1):
                if j-nums[i]>=0:
                    dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])
        if dp[target]==target:return True
        else:return False