【数据结构与算法】【LeetCode】【动态规划】416.分割等和子集

0-1背包问题思想、二维数组、滚动数组

题目

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

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200

示例1：

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例2：

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

题解

转换为0-1背包问题

「0 - 1」 背包问题的思路

0-1背包问题特点：每个数只能用一次。解决思路：物品一个一个选 ，容量一点一点增加考虑，这也是【动态规划】的思想，特别重要

实际上，尝试把候选物品放入背包，通过比较得出一个物品要不要拿走。

具体做法：
具体做法是：画一个 n 行，target + 1 列的表格。这里 n 是物品的个数，target 是背包的容量。n 行表示一个一个物品考虑，target + 1多出来的那 1 列，表示背包容量从 0 开始考虑。很多时候，我们需要考虑这个容量为 0 的数值。

状态与状态转移方程

• 状态定义：dp[i][j]表示从数组的[0, i]这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于 j。

• 状态转移方程：很多时候，状态转移方程思考的角度是「分类讨论」，对于「0-1 背包问题」而言就是「当前考虑到的数字选与不选」。

  • 不选择 nums[i]，如果在[0, i - 1]这个子区间内已经有一部分元素，使得它们的和为j，那么 dp[i][j] = true
  • 选择nums[i]，如果在 [0, i - 1]这个子区间内就得找到一部分元素，使得它们的和为 j - nums[i]

状态转移方程：

dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]

一般写出状态转移方程以后，就需要考虑初始化条件。

• j - nums[i]作为数组的下标，一定得保证大于等于 0 ，因此 nums[i] <= j
• 注意到一种非常特殊的情况：j 恰好等于 nums[i]，即单独 nums[j] 这个数恰好等于此时「背包的容积」j，这也是符合题意的。

因此完整的状态转移方程是：

$$ dp[i][j]= \begin{cases} dp[i-1][j],\quad 至少是这个答案，如果dp[i-1][j]为真，直接计算下一个状态
\ true, \quad nums[i]=j
\dp[i-1][j-nums[i]] \quad nums[i]<j\end{cases} \tag{1} $$

说明：虽然写成花括号，但是它们的关系是 或者

• 初始化：dp[0][0] = false，因为候选数 nums[0]是正整数，凑不出和为 0；
• 输出：dp[n - 1][target]，这里n 表示数组的长度，target是数组的元素之和（必须是偶数）的一半。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution:
    def canPartition(self, nums) -> bool:
        # 空的or长度为1,直接返回false
        if len(nums)<=1:
            return False
        
        # 若集合中元素和为奇数，直接返回false
        sum=0
        for i in nums:
            sum+=i
        if sum%2==1:
            return False
        
        # 处理集合元素和为偶数情况
        n= len(nums)
        target = sum//2
        
        # 创建二维状态数组，行：物品索引，列：容量（包括 0）
        dp = [[False] * (target + 1) for _ in range(n)]

        #先填表格第 0 行，第 1 个数只能让容积为它自己的背包恰好装满
        if nums[0] <=target:
            dp[0][nums[0]] = True

        for i in range(1,n):
            for j in range(target+1):
                #dp[i][j] = dp[i - 1][j]# 直接从上一行先把结果抄下来，然后再修正
                    
                if nums[i]==j:
                    dp[i][j]=True
                    continue
                if nums[i]<j:
                    dp[i][j]= dp[i-1][j] or dp[i-1][j-nums[i]]
        return dp[n-1][target]

1
2
3
4

a=Solution()
nums=[1,2,5]
result=a.canPartition(nums)
print(result)

False


target=4

3 行 5列
     0 1 2 3 4
1  0 F T F F F
2  1 F T T T F
5  2 F T T T F

复杂度分析

• 时间复杂度：O(NC)：这里 N 是数组元素的个数，C 是数组元素的和的一半。
• 空间复杂度：O(NC)。

空间优化，一维数组

「0-1 背包问题」常规优化：「状态数组」从二维降到一维，减少空间复杂度。

• 在「填表格」的时候，当前行只参考了上一行的值，因此状态数组可以只设置 2 行，使用「滚动数组」的技巧「填表格」即可；
• 实际上，在「滚动数组」的基础上还可以优化，在「填表格」的时候，当前行总是参考了它上面一行 「头顶上」 那个位置和「左上角」某个位置的值。因此，我们可以只开一个一维数组，从后向前依次填表即可。
• 「从后向前」 写的过程中，一旦 nums[i] <= j不满足，可以马上退出当前循环，因为后面的 j 的值肯定越来越小，没有必要继续做判断，直接进入外层循环的下一层。相当于也是一个剪枝，这一点是「从前向后」填表所不具备的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def canPartition(self, nums) -> bool:
        if len(nums)<=1:
            return False
        sum= 0
        for i in nums:
            sum+=i
        if sum%2==1:
            return False
        
        n= len(nums)
        target= sum//2
        
        dp=[False]*(target+1)
        dp[0]=True
        if nums[0]<=target:
            dp[nums[0]]=True
        for i in range(1,n):
            for j in range(target,0,-1):
                if dp[target]:
                    return True
                if nums[i]>j:
                    break
                dp[j]= dp[j] or dp[j-nums[i]]
                
        return dp[target]

1
2
3
4

a=Solution()
nums=[1,2,4,5]
result=a.canPartition(nums)
print(result)

True

复杂度分析

• 时间复杂度：O(NC)：这里 N 是数组元素的个数，C 是数组元素的和的一半；
• 空间复杂度：O(C)：减少了物品那个维度，无论来多少个数，用一行表示状态就够了