leetcode-416分割等和子集【dp】

解题思路：动态规划

• 两个元素和相等的子集，所以子集的值为总和sum的一半，也就是说sum必为偶数才存在题意的子集，且化简题目为求子集和为target=sum/2.
  使用动态规划（特点：不重复、无遗漏）
• 第一步：化成最后一步的子问题，且得到状态和初始化
• dp数据类型定义为boolean， boolean[] dp = new boolean[target + 1]，从boolean出发我们知道我们想要的是dp[target]，已知有num数组元素，比如{2，2，4}，返回true，那么{2,2}{4}如果元素dp[2]=true，类推到最后一步dp[target]=true时，需要怎么都拿到true？尝试设置一个dp[0]=true的初始化，利用dp[2]=dp[2-2]=true,dp[4]=[4-2]=true.ok，初始化选择true。dp[0] = true;
• 第二步：转移方程
  dp[i]=dp[target-num[i]]
• 第三步：注意不越界
  for (int j = target; j >= num; --j) { dp[j] |= dp[j - num]; }
• 第四步：不重复不遗漏

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return false;
        }
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            for (int j = target; j >= num; --j) {
                dp[j] |= dp[j - num];
            }
        }
        return dp[target];
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/fen-ge-deng-he-zi-ji-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。