C++刷leetcode（416. 分割等和子集）【动态规划】

糖逗

题目描述：

1. 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
   
2. 
   
3. 注意:
   
4. 
   
5. 每个数组中的元素不会超过 100
   
6. 数组的大小不会超过 200
   
7. 示例 1:
   
8. 
   
9. 输入: [1, 5, 11, 5]
   
10. 
    
11. 输出: true
    
12. 
    
13. 解释: 数组可以分割成 [1, 5, 5] 和 [11].
    
14.  
    
15. 
    
16. 示例 2:
    
17. 
    
18. 输入: [1, 2, 3, 5]
    
19. 
    
20. 输出: false
    
21. 
    
22. 解释: 数组不能分割成两个元素和相等的子集.
    
23. 
    
24. 来源：力扣（LeetCode）
    
25. 链接：https://leetcode-cn.com/problems/partition-equal-subset-sum
    
26. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     bool canPartition(vector<int>& nums) {
   
4.         //计算累加和
   
5.         int len = nums.size();
   
6.         vector<int>store(len+1, 0);
   
7.         store[0] = 0;
   
8.         store[1] = nums[0];
   
9.         //预判
   
10.         for(int i = 2; i <= len; i++){
    
11.             store[i] = store[i-1] + nums[i-1];
    
12.         }
    
13.         if(store[len] % 2 != 0)return false;
    
14.         vector<vector<bool> >dp(len, vector<bool>(store[len] + 1, false));
    
15.         //初始化
    
16.         for(int i = 0; i < len; i++){
    
17.             dp[i][0] = true;
    
18.         }
    
19.         dp[0][nums[0]] = true;
    
20.         //动态规划
    
21.         for(int i = 1; i < len; i++){
    
22.             for(int j = 0; j <= store[i]; j++){
    
23.                 if(dp[i-1][j] == true){
    
24.                     //不加当前
    
25.                     dp[i][j] = true;
    
26.                     //加当前
    
27.                     dp[i][j + nums[i]] = true;
    
28.                     if(j + nums[i] == store[len] / 2)return true;
    
29.                     //cout << i << " " << j << "--"<< i << " " << j + nums[i] << "--";
    
30.                 }
    
31.             }
    
32.             //cout << endl;
    
33.         }
    
34.         return false;
    
35.     }
    
36. };

复制代码