leetcode(力扣) 416. 分割等和子集 (動态規劃 & 01背包問題)

文章目錄

• ​​題目描述​​
• ​​思路分析​​
• ​​完整代碼​​

題目描述

給你一個 隻包含正整數 的 非空 數組 nums 。請你判斷是否可以将這個數組分割成兩個子集，使得兩個子集的元素和相等。

示例 1：

輸入：nums = [1,5,11,5]

輸出：true

解釋：數組可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

輸入：nums = [1,2,3,5]

輸出：false

解釋：數組不能分割成兩個元素和相等的子集。

思路分析

在做這道題之前一定要先看 ​​01背包理論基礎​​

這種題最難的不是寫代碼，也不是思路，而是怎麼模組化，要不是最近在練動态規劃，我都不一定能想到用01背包去做這個題。

題目和01背包的轉換：

題目給出一個數組nums，要求分成兩個子集，使他們相等，這裡要注意，隻能分成兩個子集。 是以問題轉化成，求一個子集 使其等于 sum(nums) // 2 == target。如果有這樣的子集 則傳回True 否則傳回False

背包容量就是 target， dp[j] 則代表 背包容量為j時能湊的最大的子集和為dp[j]，最後如果 dp[target] == target 則就是找到了某個子集使其等于目标值。

這道題裡的物品重量=物品價值=數組值=nums[i]。

動規五步走;

1.确定dp下标含義：

dp[j] 表示背包容量為 j時，最大的子集和為dp[j]，

2.确定遞推公式:

在問題轉換哪裡已經分析過了，直接拿傳統背包問題來轉換一下 就行。

遞推公式:dp[j] = max(dp[j],dp[j-nums[i]]+nums[i])

3.初始化dp

這裡的dp[j] 表示背包容量為j的最大子集和為dp[j]。

是以也就意味這容量能多大，我們初始化就得初始化多大的一維數組。

這裡要看題目給的提示。

提示：

1 <= nums.length <= 200

1 <= nums[i] <= 100

是以最大應該是20000，而我們背包隻需要一半的容量，直接初始化10000個[0]的一維數組就行了。

完整代碼

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
            if sum(nums) % 2 == 1:
                return False
            target = sum(nums) // 2
            dp = [0] * 10000
            # dp[i] 表示背包容量i 裡的最大子集是dp[i]
            # 先物品，再背包，這裡就想那個二維的數組格子就行了。
            for i in range(len(nums)):
                for j in range(target,nums[i]-1,-1):  # j表示背包容量，你的j必須大于目前周遊i的重量,才有往後的意義。
                    dp[j] = max(dp[j],dp[j-nums[i]]+nums[i])
            return dp[target] == target