Leetcode 494 目标和

题意理解：

????????给你一个非负整数数组?nums?和一个整数?target?。

????????向数组中的每个整数前添加?'+'?或?'-'?，然后串联起所有整数，可以构造一个?表达式?：

• 例如，nums = [2, 1]?，可以在?2?之前添加?'+'?，在?1?之前添加?'-'?，然后串联起来得到表达式?"+2-1"?。

????????返回可以通过上述方法构造的、运算结果等于?target?的不同?表达式?的数目。

????????

? ? ? ? 简单来说：就是在元素前面加‘+’或‘-’使其结果值为target。

? ? ? ? 可以将其思路转换为：将数组元素分为两部分，其差为target。

? ? ? ? 则有part1-part2=target，part1+part2=sum

? ? ? ? part1=(sum+target)/2

????????

? ? ? ? 固有我们需要将数组元素分为两部分，一部分较大的为part1=(sum+target)/2,较小的部分为part2=(sum-target)/2。

? ? ? ? 此时，我们再次转变思路：将其构造成0-1背包问题：

? ? ? ? 背包大小为m=(sum+target)/2

? ? ? ? 物品为[0,n]的元素，其价值和重量都是nums[]

? ? ? ? 接下来，使用动态规划中的0-1背包思路解决问题。

解题思路：

? ? ??首先理解题意，将其转换为一个背包问题，使用动态规划的思路来求解。

? ? ? ? ?动态规划五部曲：

? ? ? ? （1）dp[i][j]或dp[i]的含义

? ? ? ? （2）递推公式

? ? ? ? （3）根据题意初始化

? ? ? ? （4）遍历求解:先遍历包还是先遍历物品

? ? ? ? （5）打印——debug

1.动态规划二维dp数组

1. dp[i][j]表示[0,i]的元素装满大小为j的背包有多少种方法。
2. 递推公式：dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]]?????????????，
   1. 当当前物品大于当前背包的大小时，放满大小为j的背包的方法数仍就为dp[i-1][j].
   2. 当当前物品小于等于当前背包的大小时，放满大小为j的背包的方法数=dp[i-1][j]+dp[i-1][j-nums[i]]，其中dp[i-1][j-nums[i]]是增加了物品nums[i]后增加的方法数。?????????????
3. 初始化：初始化第一列，其中特别的：放满背包大小0 有多少种方法——要么什么也不放，要么放入大小为0的物品。初始化时要根据问题，具体分析。
4. 遍历：由于二维数组保留了两个维度所有值，所以先便利包还是先遍历物品都可以

public int findTargetSumWays(int[] nums, int target) {
        int sum=0;
        for(int num:nums){
            sum+=num;
        }
        //是否能按照需求分成两部分
        if((sum+target)%2!=0) return 0;
        if((sum-target)%2!=0) return 0;
        //把所有值当作整数，分成两部分一正一负即可，所以如果target总保持为正数
        if(target<0) target=-target;
        int size= (int)Math.ceil((float)(sum+target)/2);
        int dp[][]=new int[nums.length][size+1];
        //初始化
        for(int[] temp:dp) Arrays.fill(temp,0);
        int countZero=0;
        for(int i=0;i<nums.length;i++){
           if(nums[i]==0) countZero++;
           dp[i][0]=countZero+1;
        }
        for(int j=1;j<=size;j++){
            if(nums[0]==j) dp[0][j]=1;
            else dp[0][j]=0;
        }
        //遍历顺序
        for(int i=1;i< nums.length;i++){
            for(int j=0;j<=size;j++){
                if(j<nums[i]){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=dp[i-1][j]+dp[i-1][j - nums[i]];
                }
            }
        }
        return dp[nums.length-1][size];
    }

2.一维滚动数组——存储压缩

1. dp[j]表示装满大小为j的背包有多少种方式。
2. 递推公式：dp[j]=max(dp[j],dp[j-weight[i]]+values[i])
3. 初始化：右边的值总是由最左边的值推导而来,dp[0]表示使背包价值为0有多少种放置方法——要么什么也不放，要么放大小为0的物品。
4. 遍历：由于以为滚动数组是二维dp数组的动态行滚动更新，所以遍历顺序总是先物品后背包。
5. 注意：为了防止用同层修改过的值修改本行其他值，导致物体重复放置，故采用倒序遍历背包。

 public int findTargetSumWays(int[] nums, int target) {
        int sum=0;
        for(int num:nums) sum+=num;
        if((sum+target)%2!=0) return 0;
        if((sum-target)%2!=0) return 0;
        if(target<0) target=-target;
        int size= (int)Math.ceil((float)(sum+target)/2);
        int dp[]=new int[size+1];
        //初始化
        Arrays.fill(dp,0);
        dp[0]=1;
        //遍历顺序
        for(int i=0;i< nums.length;i++){
            for(int j=size;j>=nums[i];j--){
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[size];
    }

3.分析

时间复杂度：O()

空间复杂度：

? ? ? ? 二维：O(n*size)

? ? ? ? 一维：O(size)