淮安市建设工程质量监督站网站,wordpress 全屏浮动,手机可以搭建网站吗,网站建设都包含哪些内容LeetCode 416. 分割等和子集
题目描述
给你一个 只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集#xff0c;使得两个子集的元素和相等。
思路
和LeetCode 494.目标和很相似#xff0c;这道题也是用动态数组可以求解的。
对nums的所有元素求个…LeetCode 416. 分割等和子集
题目描述
给你一个 只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
思路
和LeetCode 494.目标和很相似这道题也是用动态数组可以求解的。
对nums的所有元素求个sum若sum % 2 ! 0则return false; 因为此时没办法分成两个等和子集定义dp数组dp[nums.length][bagSize 1]其中bagSize sum / 2;初始化dp数组dp[0][nums[0]]1;填充dp数组嵌套循环有两种可能性 I. nums[i] j时dp[i][j]dp[i-1][j] II. 否则求最值dp[i][j]Math.max(dp[i-1][j], dp[i-1][j-nums[i]]nums[i])返回dp[nums.length-1][bagSize]bagSize为什么这里的递推式是求“最值”我的理解是任何一个值都有可能是构成目标和的一部分
当然这可以用一维dp来解因为nums[i]里面的数既是重量也是价值但是我赶时间就没细看
代码
class Solution {public boolean canPartition(int[] nums) {int sum 0;for (int num : nums) {sum num;}if (sum % 2 ! 0) return false; // 和无法评分则无法分成两个相等的子集int bagSize sum / 2; // 目标和的结果// 动态数组定义与初始化int[][] dp new int[nums.length][bagSize 1];if (nums[0] bagSize) dp[0][nums[0]] 1;// 填充动态数组for (int i 1; i nums.length; i) {for (int j 1; j bagSize 1; j) {if (nums[i] j) dp[i][j] dp[i - 1][j];else {dp[i][j] Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] nums[i]);}}}return dp[nums.length - 1][bagSize] bagSize;}
}
