【力扣刷题 | 第二十四天】

Myth丶恋晨 2023-10-14 13:16 26阅读 0赞

![7ffdd5d28e2f4eb6933345ddbeb147e7.jpeg][]

**目录**

前言：

416. 分割等和子集 - 力扣（LeetCode）

总结

--------------------

## 前言： ##

今晚我们爆刷动态规划类型的题目。

## [416. 分割等和子集 - 力扣（LeetCode）][416. _ - _LeetCode] ##

给你一个 **只包含正整数** 的 **非空** 数组 `nums` 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

![e04861dd5acb4800bf69836eded42f43.png][]

这道题其实可以用我们之前讲过的回溯算法暴力搜索来做，其基本思想为：我们先对这个数组求和，之后再除以二，此时如果我们如果我们得到了一个整数，就说明这个数组是可以分为两个元素和一样的子集的，如果得不到就说明这个数组根本就没有办法被均分，自然也就无法得到两个元素和一样的子集。

那么也就是说把这个集合的总和的一半target求出来，然后在集合中搜索，如果可以在原集合中找到一个子集的和==target，那么另一半子集的和自然也就是target。

因此我们简化了这个问题，现在我们要做的是：

> **在这个集合中找出一个子集，使得子集的和等于target**

但问题是使用回溯算法暴力搜索的话，就这道题而言，会超时。因此我们就要再想想还有没有别的方法

答案是有的。其实我们可以把他想为一个背包问题：一共有这么多的数，能否把容量为target的包满

那么不就是一个动态规划的问题嘛那么我们就开始动态规划的五步：  
1.确定dp数组的含义以及下标含义：

dp\[j\] 容量为j的背包 能够容纳的最多价值为 dp\[j\],而这道题我们可以认为每一个元素的数值即是容量也是价值

如果我们把11这个背包装满之后，他的价值也是11，那么就说明存在一个子集，他的元素和为target

2.状态转移方程：dp\[j\]= max(dp\[j\] , dp\[j-nums\[i\]\]+nums\[i\[);

因此我们可以得到代码：

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

## 总结 ##

动态规划的题目更加灵活多变，有的时候很难想出来这还能用动态规划的思路来做，因此我们要多做多练，才可以学好动态规划。

如果我的内容对你有帮助，请**点赞，评论，收藏**。创作不易，大家的支持就是我坚持下去的动力！

![69e9169c980f43e0aad31ff9ada88a9c.png][]

[7ffdd5d28e2f4eb6933345ddbeb147e7.jpeg]: https://img-blog.csdnimg.cn/7ffdd5d28e2f4eb6933345ddbeb147e7.jpeg
[416. _ - _LeetCode]: https://leetcode.cn/problems/partition-equal-subset-sum/
[e04861dd5acb4800bf69836eded42f43.png]: https://img-blog.csdnimg.cn/e04861dd5acb4800bf69836eded42f43.png
[69e9169c980f43e0aad31ff9ada88a9c.png]: https://img-blog.csdnimg.cn/69e9169c980f43e0aad31ff9ada88a9c.png