416. 分割等和子集(leetcode)

https://leetcode.cn/problems/partition-equal-subset-sum/description/

01背包问题,需要考虑到如何把这个问题转化成01背包问题
转换成01背包问题后,如何定义f[i]状态来表示

这里有两种方式:1.按照传统01背包表示,即前i个物品中选,体积小于等于j的最大价值,这里体积和价值是等价的
2.按照标准定义来:f[i][j]表示能否选出 在 前i个数中,和正好为j 的序列,这里仍以第i个数选或者不选来划分子集
可得f[i][j] = f[i-1][j-nums[i]] || f[i-1][j]  ,即若选第i个数,则需要知道 f[i-1][j-nums[i]] 能否凑出, 若不选, 则需要知道 f[i-1][j],能否凑出,这两个子集有一个可以即可

class Solution {
    public boolean canPartition(int[] nums) {
        // f[i][j] 表示前i个物品中选，体积小于等于j的所有选法的集合,表示的属性是最大价值
        // f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i])
        // 计算出f[i][j]后,根据f的定义可以知,选取出target的最大价值是:f[nums.length-1][target],判断这个最大价值是否是target
        // 即可判断这个数组能否选出来两个和为target的子数组
        int sum=0;
        int[][] f = new int[210][20010];
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) return false;
        int target = sum / 2;
        for(int i=1;i<nums.length;i++)
            for(int j=0;j<=target;j++)
            {
                f[i][j]=f[i-1][j];
                if(j>=nums[i])
                    f[i][j] = Math.max(f[i-1][j],f[i-1][j-nums[i]]+nums[i]);
            }
        return f[nums.length-1][target] == target;
    }
}

class Solution {
    public boolean canPartition(int[] nums) {
        // 求两个子集元素和相等,则可以求出这个和是sum(nums)/2
        // 剩余就是求在nums中选择若干数使得和正好为目标值
        // f[i][j]表示在前i个数中选择,和正好等于j的选法,f[i][j]表示的意思是
        // 前i个数中选择,和为j是否能够凑齐
        // 以第i个数选或者不选 来划分子集
        // f[0][0]=true
        // f[i][j] = f[i-1][j-nums[i]] || f[i-1][j]
        int target=0;
        for(int i=0;i<nums.length;i++)target+=nums[i];
        if(target%2==1)return false; // 不可能划分的情况
        target/=2;
        boolean[][] f = new boolean[nums.length+1][200*100+1];
        f[0][0]=true;
        for(int i=0;i<nums.length-1;i++)
            for(int j=0;j<=target;j++)
                if(j>=nums[i])f[i+1][j] = f[i][j-nums[i]] || f[i][j];
                else f[i+1][j]=f[i][j];

                
        return f[nums.length-1][target];
    }
}