企慕网站建设网络推广,网站群系统建设的目的,phpwind 做企业网站,甘肃省城乡住房建设厅网站首页个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程#xff0c;希望… 个人主页兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 点击直接跳转到该题目 目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码 1️⃣题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
示例1 输入nums [1,5,11,5] 输出true 解释数组可以分割成 [1, 5, 5] 和 [11] 。 示例2 输入nums [1,2,3,5] 输出false 解释数组不能分割成两个元素和相等的子集。 注意
1 nums.length 2001 nums[i] 100
2️⃣题目解析
状态表示
dp[i][j]从前i个数中进行挑选能够凑成j这个数。
状态转移方程
如果不挑选第i个数则dp[i][j] dp[i - 1][j]如果挑选第i个数且j nums[i]则dp[i][j] dp[i - 1][j] || dp[i - 1][j - nums[i]]
3️⃣解题代码
class Solution {
public:bool canPartition(vectorint nums) {int n nums.size(), sum 0;for(auto x : nums) sum x;if(sum % 2 1) return false;vectorvectorbool dp(n 1,vectorbool(sum / 2 1));for(int i 0;i n;i) dp[i][0] true;for(int i 1;i n;i){for(int j 1;j sum / 2;j){dp[i][j] dp[i - 1][j];if(j nums[i - 1]) dp[i][j] dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];}}return dp[n][sum / 2];}
};最后就通过啦
