[数据结构与算法]【LeetCode】Day145-分割等和子集

题目

416. 分割等和子集【中等】

题解

看着挺典型的动态规划问题，可以将其转换为 0-1背包问题。传统的「0?1 背包问题」要求选取的物品的重量之和不能超过背包的总容量，这道题则要求选取的数字的和恰好等于整个数组的元素和的一半。

算法
对于数组元素个数n，元素和sum以及最大元素max，首先进行一些判断，类似于剪枝操作：

• n<2，直接返回false；
• sum是奇数，直接返回false；
• sum是偶数，令target=sum/2；
• max>target，说明其它元素之和一定小于target，返回false

之后再利用动态规划求解，

1. 状态定义：dp[i][j] 表示区间 [0,i] 选取若干个正整数，是否存在方案使得被选取的正整数之和等于 j。所以二维dp包含n行 target+1列。
2. 状态转移方程：
   如果 j<nums[i]，说明nums[i]太大了，选上他总和会超，一定不能选，dp[i][j] = dp[i-1][j]。
   如果 j>=nums[i]，那么nums[i]可选可不选，有两种选择，
   若选取nums[i]：dp[i][j] = dp[i-1][j-nums[i]]；
   若不选nums[i]：dp[i][j] = dp[i-1][j]。
3. 初始条件：
   dp[i][0]=true，从[0,i]区间中选0个正整数就可以使之和为0，因此为true；
   dp[0][nums[0]]=true，在[0,0]区间中只选取nums[0]就可以使之和为nums[0]，因此为true；
   其余dp[i][j]=false。
4. 返回值：dp[n-1][target]，target=sum/2

class Solution {
    public boolean canPartition(int[] nums) {
        /*一些特殊判断*/
        int n=nums.length,sum=0,max=0;
        for(int num:nums){
            sum+=num;
            max=Math.max(max,num);
        }
        int target=sum/2;
        if(n<2||sum%2==1||max>target)
            return false;
        
        /*动态规划*/
        boolean[][] dp=new boolean[n][target+1];
        //dp初始条件
        dp[0][nums[0]]=true;
        for(int i=0;i<n;i++)
            dp[i][0]=true;
        //状态转移
        for(int i=1;i<n;i++){
            for(int j=1;j<=target;j++){
                int num=nums[i];
                if(num>j)
                    dp[i][j]=dp[i-1][j];
                else
                    dp[i][j]=dp[i-1][j]|dp[i-1][j-num];
            }
        }
        return dp[n-1][target];
    }
}

改进
在计算过程中，每一行dp都只与上一行有关，因此可以优化空间复杂度，将dp降至一维数组，转移方程变为dp[j]=dp[j] | dp[j-nums[i]]。
需要注意的是，此时对于 j 的遍历需要从大到小进行，才能保证需要dp[j-nums[i]]时，它是上一行的值，而不是在本行更新过的值。

class Solution {
    public boolean canPartition(int[] nums) {
        /*一些特殊判断*/
        int n=nums.length,sum=0,max=0;
        for(int num:nums){
            sum+=num;
            max=Math.max(max,num);
        }
        int target=sum/2;
        if(n<2||sum%2==1||max>target)
            return false;
        
        /*动态规划*/
        boolean[] dp=new boolean[target+1];
        //dp初始条件
        dp[0]=true;
        //状态转移
        for(int i=1;i<n;i++){
            int num=nums[i];
            for(int j=target;j>=num;j--){
                dp[j]=dp[j]|dp[j-num];
            }
        }
        return dp[target];
    }
}

时间复杂度：$O(n?target)$

空间复杂度：$O(target)$