动态规划---分割等和子集

题目：给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

思路：

本题可理解为01背包问题，背包容量为Nums数组和的一半，物品是Nums数组的元素。

动态规划五部曲：

1.确定dp数组及其含义。dp数组为一维数组（滚动数组），等价于dp数组为二维数组时把i-1行的数据拷贝到i行，把矩阵压缩为一行。dp[j]代表背包最大容量为j时，背包的最大价值。

2.推导递推公式。本题是背包里放入数值，物品i的重量是nums[i]，价值也是nums[i]，所以递推公式为dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])   

dp为二维数组时dp[i][j]=max(dp[i-1][j],dp[i][j-weight[i]]+value[i])，本题中weight数组=value数组=nums数组。dp[i][j]的含义是把0~i的物品尽量放入到容量为j的背包中，背包的最大价值。

3.dp数组初始化。题目给的价值都是正整数，所以dp数组初始化为0即可。如果有负数，要将对应的dp元素初始化为负无穷。根据第二步的递推公式，这样处理才不会覆盖掉递推推导出的数值。

4.确定遍历顺序。使用一维dp数组，要将物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历。

倒序遍历保证了每个物品只被添加了一次。例如第5步中的例子，如果使用正序遍历，进入for循环有dp[0]=dp[0]=0,dp[1]=dp[1-1]+nums[0]=5,dp[2]=dp[2-1]+nums[0]=10,很明显第一个物品5被加了两次。

5.举例推导dp数组。例如nums=[1,5,11,5]，dp=[0,1,1,1,1,5,6,6,6,6,10,11]

如果dp数组最后一个元素的值正好是Nums数组和的一半，即最大价值等于背包容量，则返回true

代码：

    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int num:nums){
            sum+=num;
        }
        if(sum%2!=0) return false;//和为奇数不可能平分成两份
        int target=sum/2;//背包容量
        int[] dp=new int[target+1];
        for(int i=0;i<nums.length;i++){//遍历物品（nums数组元素）
            for(int j=target;j>=nums[i];j--){//遍历背包容量，倒序
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if(dp[target]==target) return true;
        return false;
    }