云主机可以放多少网站,抖音代运营费用大概多少,广东造价信息网,国内响应式网站建设目录 前言#xff1a;
416. 分割等和子集 - 力扣#xff08;LeetCode#xff09;
总结 前言#xff1a; 今晚我们爆刷动态规划类型的题目。
416. 分割等和子集 - 力扣#xff08;LeetCode#xff09;
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这…
目录 前言
416. 分割等和子集 - 力扣LeetCode
总结 前言 今晚我们爆刷动态规划类型的题目。
416. 分割等和子集 - 力扣LeetCode
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 这道题其实可以用我们之前讲过的回溯算法暴力搜索来做其基本思想为我们先对这个数组求和之后再除以二此时如果我们如果我们得到了一个整数就说明这个数组是可以分为两个元素和一样的子集的如果得不到就说明这个数组根本就没有办法被均分自然也就无法得到两个元素和一样的子集。 那么也就是说把这个集合的总和的一半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(vectorint nums) {int sum0;vectorint dp(10001, 0);for (int i 0; i nums.size(); i) {sum nums[i];}if(sum%21){return false;}int target sum/2;for(int i0;inums.size();i){for(int jtarget;jnums[i];j--){dp[j] max(dp[j],dp[j-nums[i]]nums[i]);}}if(dp[target]target){return true;}else{return false;}}
};
总结 动态规划的题目更加灵活多变有的时候很难想出来这还能用动态规划的思路来做因此我们要多做多练才可以学好动态规划。
如果我的内容对你有帮助请点赞评论收藏。创作不易大家的支持就是我坚持下去的动力
