416. 分割等和子集 (opens new window)

1.动态规划

解题关键在于能否进一步将问题抽象和转化为背包问题：

• 将数组分割成两个元素之和相等的子集<= ==等价于== =>从数组中取出任意数量的元素，使取出的所有元素之和等于剩下元素之和。
• 每个元素存在两种操作，取或不取。如果当前nums[ i ]元素能够使当前元素和等于target，那么说明在前面遍历的过程中，当前元素和也肯定等于过target-nums[ i ]。使用到了子问题的解，因此使用动态规划。

定义dp[ i ][ j ]表示前 i 种物品的组合是否能够使当前元素之和等于 j 。显然对于第i种物品而言，仅存在取或不取两种情况，因此状态转移方程为：dp[ i ][ j ]= dp[i-1][j] || dp[i-1][j-nums[i]]

题目做法的本质就是开辟一个空间，保存当前元素相加后所能产生的新的和。

class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        if(sum%2==1) return false;

        int target=sum/2;
        boolean[][] dp=new boolean[nums.length][target+1];

        for(int i=0;i<nums.length;i++){
            //前i个数都不取和为0，置为true
            dp[i][0]=true;
            for(int j=0;j<=target;j++){
                //取第一个数进行初始化
                if(i==0){
                    dp[i][j]=nums[i]==j?true:false;
                    continue;
                }
                dp[i][j]=dp[i][j]||dp[i-1][j];
                if(j-nums[i]>=0){
                    dp[i][j]=dp[i][j]||dp[i-1][j-nums[i]];
                }
            }
        }
        return dp[nums.length-1][target];
    }
}

2.动态规划空间优化

dp状态数组从二维降到一维：dp数更新优化采用逆序的方式，必须保证当前dp[i]更新时，用到的只能是上一层外循环中的状态(每个元素只能被选择一次)。因为对于每一层外循环，当前元素最多只能够放一次。如果是从小到大循环，那么当前 j 可能会用到本轮循环前面刚更新过的值。

 dp[j] （新）= dp[j] （旧） || dp[j - nums[i]] （旧）