建设网站费用要进固定资产吗,班级网站策划书,河南省建设工程造价协会网站,宿迁房产网丫丫找房题目
使用二维dp数组思路 首先#xff0c;我们需要计算整个数组的元素和 total_sum。如果 total_sum 是奇数#xff0c;那么无论如何都无法将数组分成两个和相等的子集#xff0c;因此直接返回 false。 然后#xff0c;我们定义一个二维布尔数组 dp#xff0c;其中 dp[i]…题目
使用二维dp数组思路 首先我们需要计算整个数组的元素和 total_sum。如果 total_sum 是奇数那么无论如何都无法将数组分成两个和相等的子集因此直接返回 false。 然后我们定义一个二维布尔数组 dp其中 dp[i][j] 表示前 i 个元素是否可以组成和为 j 的子集。 初始化 dp[0][0] 为 true表示不选择任何元素时可以得到和为 0 的子集。对于其他的 dp[i][0]它们也为 true因为不选择任何元素时可以得到和为 0 的子集。 对于每个元素 nums[i]我们遍历从 0 到 total_sum / 2 的所有可能的和 j。如果 dp[i-1][j] 为 true说明前 i-1 个元素已经可以组成和为 j 的子集那么第 i 个元素 nums[i] 不选择时前 i 个元素也可以组成和为 j 的子集如果 dp[i-1][j-nums[i]] 为 true说明前 i-1 个元素已经可以组成和为 j-nums[i] 的子集那么加上第 i 个元素 nums[i] 后前 i 个元素也可以组成和为 j 的子集。 最后如果 dp[nums.size()-1][total_sum/2] 为 true说明前 nums.size()-1 个元素可以组成和为 total_sum/2 的子集那么整个数组也可以分割成两个和相等的子集返回 true否则返回 false。
代码实现
class Solution {
public:bool canPartition(vectorint nums) {int total_sum 0;for (int num : nums) {total_sum num;}if (total_sum % 2 1) {return false;}int target_sum total_sum / 2;vectorvectorbool dp(nums.size(), vectorbool(target_sum 1, false));dp[0][0] true;for (int i 1; i nums.size(); i) {dp[i][0] true;}for (int i 1; i nums.size(); i) {for (int j 1; j target_sum; j) {if (j nums[i]) {dp[i][j] dp[i-1][j] || dp[i-1][j-nums[i]];} else {dp[i][j] dp[i-1][j];}}}return dp[nums.size()-1][target_sum];}
};使用一维dp数组思路 本题可以等效为01背包问题定义dp[j]为容量为j的背包最大价值为dp[j]. 同上思路算出总和的一半为target遍历建立递推公式dp[j] max(dp[j], dp[j - nums[i]] nums[i]);如果dp[target]target则说明满足条件。
代码实现
class Solution {
public:bool canPartition(vectorint nums) {int sum 0;// dp[i]中的i表示背包内总和// 题目中说每个数组中的元素不会超过 100数组的大小不会超过 200// 总和不会大于20000背包最大只需要其中一半所以10001大小就可以了vectorint dp(10001, 0);for (int i 0; i nums.size(); i) {sum nums[i];}if (sum % 2 1) return false;int target sum / 2;// 开始 01背包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]);}}// 集合中的元素正好可以凑成总和targetif (dp[target] target) return true;return false;}
};
