---

---

一、分割等和子集-LeetCode 416

Leecode鏈接: leetcode 416
文章鏈接: 代碼隨想錄
視頻鏈接: B站

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

示例1：

輸入：nums = [1,5,11,5]
輸出：true
解釋：數組可以分割成 [1, 5, 5] 和 [11] 。

思路

本體可以看作一個背包模型，將數組總和除2，將總和一半定義為背包的容量，數組元素為可選的物品。本題既可以定義一個一維dp數組，也可以定義一個二維dp數組，但二維便于理解與講解并且一維只是二維的精簡版，思想基本一致，所以主要寫一下二維的思路。數組形式為dp[i][j]，i為可選的物品范圍，例如當i為3時，表示可選的物品范圍為0到3下標的物品任意物品；j表示當前背包的容量大小。dp數組含義為，在j容量下，物品0到i范圍可以獲得的最大和。遞推公式為dp[i][j] = dp[i-1][j]或dp[i][j] = max(dp[i-1][j] , dp[i-1][j-nums[i]] + nums[i])。前者表示不放的情況，后者表示物品放入后可能的情況。不放的條件就是背包容量不足以放下物品，放物品的條件就是當前背包的容量大于或等于當前物品的重量。

實現代碼

1.二維dp代碼

//cpp
class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;int len = nums.size();//物品的數量for(int a:nums){sum += a;} if(sum%2 == 1) return false;int target = sum/2;//既是物品的價值也是物品的重量vector<vector<int>>dp(len,vector<int>(target+1,0));for(int j = nums[0];j<=target;j++){dp[0][j] = nums[0];}for(int i = 1;i<len;i++){for(int j = 0;j<=target;j++){if(j<nums[i]){dp[i][j] = dp[i-1][j];}else {dp[i][j] = max(dp[i-1][j],dp[i-1][j - nums[i]]+nums[i]);}}}if(dp[len-1][target] == target) return true;return false;}
};

2.一維dp代碼

//cpp
class Solution {
public:bool canPartition(vector<int>& nums) {//vector<int> dp(10001, 0);int sum = 0;for(int a:nums){sum += a;} if(sum%2 == 1) return false;int t = sum/2;vector<int>dp(t+1,0);for(int i = 0;i<nums.size();i++){for(int j = t;j>=nums[i];j--){dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);}}if(dp[t] == t) return true;return false;}
};

問題

代碼實現細節不熟練，比如初始化時，怎么將第一行的哪些數初始化為恒定值。

總結

一維與二維的區別在于：省去了多余空間的使用，并且改變了遍歷順序，這是因為如果跟二維數組一樣從前往后遍歷，就會導致重復選擇同一個物品。比如，當i = 1時，dp[1] = 1、dp[2] = 1;當i = 2時，dp[1] = 1、dp[2] = 2，顯然是不對的因為一件物品只能選一次。雖然一維省去了空間，但時間復雜很高，leetcode上一維dp的執行用時為300ms左右，空間占用達到了10MB左右；二維dp為100ms左右，同樣的二維空間占用達到了98MB左右。

---