动态规划巧解数组等分问题
LeetCode416给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。示例 1输入nums [1,5,11,5]输出true解释数组可以分割成 [1, 5, 5] 和 [11] 。示例 2输入nums [1,2,3,5]输出false解释数组不能分割成两个元素和相等的子集。思路分割为两个相等的字串要满足和为偶数而且只要有一部分能凑出一半另一部分就一定能凑出一半采用动态规划的决策树。Python解法class Solution: def canPartition(self, nums: List[int]) - bool: s sum(nums) if s % 2 ! 0: return False target s // 2 dp [False] * (target 1) dp[0] True for num in nums: dp_tmp dp.copy() for i in range(target 1): if dp[i] and i num target: dp_tmp[i num] True dp dp_tmp if dp[target] True: return True return dp[target]Java解法class Solution { public boolean canPartition(int[] nums) { int s 0; for(int num : nums){ s s num; } if(s % 2 ! 0)return false; int target s / 2; boolean[] dp new boolean[target 1]; dp[0] true; for(int num : nums){ boolean[] dp_tmp dp.clone(); for(int i 0; i target; i){ if(dp[i] i num target){ dp_tmp[i num] true; } } dp dp_tmp; if(dp[target] true)return true; } return dp[target]; } }C解法class Solution { public: bool canPartition(vectorint nums) { int s 0; for(int num : nums){ s s num; } if(s % 2 ! 0) return false; int target s / 2; vectorbool dp(target 1, false); dp[0] true; for(int num : nums){ vectorbool dpTmp dp; for(int i 0; i target; i){ if(dp[i] i num target){ dpTmp[i num] true; } } dp dpTmp; if(dp[target]) return true; } return dp[target]; } };代码过程举例样例一nums[1,5,11,5]target11初始 dp[T,F,F,F,F,F,F,F,F,F,F,F]第一轮 num1dp_tmp [T,F,F,F,F,F,F,F,F,F,F,F]i0dp [0]Ti11 → dp_tmp [1]Tdp 更新[T,T,F,F,F,F,F,F,F,F,F,F]第二轮 num5dp_tmp [T,T,F,F,F,F,F,F,F,F,F,F]i0dp [0]T → i55 → dp_tmp [5]Ti1dp [1]T → i56 → dp_tmp [6]Tdp 更新[T,T,F,F,F,T,T,F,F,F,F,F]第三轮 num11dp_tmp [T,T,F,F,F,T,T,F,F,F,F,F]i0dp [0]T → i1111 → dp_tmp [11]T dp [11]True直接 return True样例二nums [2,3,4,5] 总和 14target7 初始 dp [T,F,F,F,F,F,F,F]第一轮 num2dp_tmp [T,F,F,F,F,F,F,F]i0dp[0]T → i22 → dp_tmp[2]Tdp [T,F,T,F,F,F,F,F]第二轮 num3dp_tmp [T,F,T,F,F,F,F,F]i0 → 033 → Ti2 → 235 → Tdp [T,F,T,T,F,T,F,F]第三轮 num4dp_tmp [T,F,T,T,F,T,F,F]i0→4T i2→6T i3→7T dp [7]True直接返回 True 最终 dp[T,F,T,T,T,T,T,T]
