关于动态规划:动态规划LeetCode-416分割等和子集

原文归档：「烤冷面讲算法，每周一讲」
原文链接：「动静布局」LeetCode 416(宰割等和子集)

LeetCode 416

上一周讲了 01 背包问题，这周咱们趁热打铁，用 01 背包问题的思路来解决 LeetCode 416 题。

题干简述

给定：一个只蕴含正整数的非空数组 nums。

要求：判断 nums 是否能够被宰割成 元素和相等 的两个子集。

题目详情：416. 宰割等和子集

解题思路

1. 解题的关键在于咱们是否从 nums 中找出一些元素，「元素的和」等于「总和」的一半，如果找失去，答案即为 true，否则就是 false。
2. 依据第 1 点，咱们能够把这道题转化为 01 背包问题，背包容量 =nums 元素和 /2，物品就是 nums 数组 中的每个元素，物品的分量和价值相等，等于元素的值(也就是 nums[i])。

除此之外还有一些边界条件：

1. 首先，nums 中所有元素的和 必须为 偶数 ，否则不可能被宰割成 元素和相等 的两个子整数集。
2. 其次，若 nums 中某个元素的值 >总元素和 /2，间接 return false。

图解算法

官网案例:

Input: nums = [1,5,11,5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

就像「01 背包问题」这篇文章提到的那样，咱们能够画出这样一个矩阵：

代码实现

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        target = s // 2
        
        # 边界值检测
        if s % 2 == 1:
            return False

        # 边界值检测
        maxNum = 0
        for num in (nums):
            maxNum = max(num, maxNum)
        if maxNum > target:
            return False

        dp = [([0] * target) for p in range(len(nums))]
        # 填充矩阵第一行
        for j in range(0, target):
            subTarget = j + 1
            if subTarget >= nums[0]:
                dp[0][j] = nums[0]

        # 填充矩阵残余所有行
        for i in range(1, len(nums)):
            num = nums[i]
            for j in range(0, target):
                subTarget = j + 1
                if subTarget > num:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-num]+num)
                elif subTarget == num:
                    dp[i][j] = num
                else:
                    dp[i][j] = dp[i - 1][j]
            if dp[i][target-1] == target:
                return True

        return False

复杂度

工夫复杂度 O(n^2)，空间复杂度 O(n^2)，在 LeetCode 下面的体现并不现实：

网上还是有不少优化计划的，比方将二维数组优化为一维数组，空间复杂度从 O(n^2)降到 O(n)。

不过这篇文章的本意在于利用上一篇「01 背包问题」学到的货色来解决 LeetCode 中相干的题目，所以先不开展讲了，当前有机会再探讨这个话题。

最初分享一个不止聊算法的圈子：「Script Run 技术社群」