关于动态规划:动态规划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 技术社群」