416. 分割等和子集(中等）-动态规划

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等

分析

• 0-1背包问题，物品就是数组的元素，体积就是物品元素的大小，条件就是能达到特定的体积大小
• 优化方案，右2维降低到1维度，然后再由1维度倒着计算

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # 0-1背包问题
        all_sum = sum(nums)
        if all_sum % 2 == 1: return False

        target = all_sum // 2
        n = len(nums)
        dp = [False for _ in range(target + 1)]
        dp[0] = True


        for i in range(1, n + 1):
            num = nums[i-1]
            # 陷阱1，需要倒着计算
            # 优化方案路线，先变成1维，然后再变成倒着计算
            for j in range(target, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]

        return dp[target]