文章目录

• 二维数组版本
• 二维数组升级版
• 一维数组版

这道题其实是一个01背包问题，只是加了一点的小变形而已
现在考虑：
怎么可以将这个变为从n个数中挑选出target个重量的组合数

可以将数分为两组,一组是符号是+的为left,一组是符号为-的为right
sum=left+right
target=left-right
所以,我们真正的target就是left=(sum+target)/2,我们要做的就是从上面的数组中挑选出满足加起来的重量是target的组合数

二维数组版本

class Solution {    public int findTargetSumWays(int[] nums, int target) { if(nums==null||nums.length==0)     return 0; int n=nums.length; //下面是计算出真正的target： int sum=0; for(int i=0;i<n;i++){     sum+=nums[i]; } //特殊情况: if(target>sum||target<-1*sum||(target+sum)%2==1)     return 0; target=(target+sum)/2; int[][] f=new int[n+1][target+1]; f[0][0]=1; for(int i=1;i<=target;i++){     f[0][i]=0; } for(int i=1;i<=n;i++){     for(int j=0;j<=target;j++){  f[i][j]=f[i-1][j];  if(j>=nums[i-1])      f[i][j]+=f[i-1][j-nums[i-1]];     } } return f[n][target];    }}

二维数组升级版

上面的空间复杂度是O(MN)
但是我们还可以进行简化成f[2][N]

我们观察到f[i][j]只是和它的上一层的f[i-1][j]和f[i-1][j-nums[i-1]]有关
所以说我们就可以只开辟一个2*n的数组进行滚动就可以了

这里我们使用old和new1来表示上一层和本层,这样就简化了时间复杂度

class Solution {    public int findTargetSumWays(int[] nums, int target) { if(nums==null||nums.length==0)     return 0; int n=nums.length; //下面是计算出真正的target： int sum=0; for(int i=0;i<n;i++){     sum+=nums[i]; } //特殊情况: if(target>sum||target<-1*sum||(target+sum)%2==1)     return 0; target=(target+sum)/2; int[][] f=new int[2][target+1]; f[0][0]=1; for(int i=1;i<=target;i++){     f[0][i]=0; } int old=0,new1=0; for(int i=1;i<=n;i++){     old=new1;     new1=1-old;     for(int j=0;j<=target;j++){  f[new1][j]=f[old][j];  if(j>=nums[i-1])      f[new1][j]+=f[old][j-nums[i-1]];     } } return f[new1][target];    }}

一维数组版

上面的代码简化了不少,但是还可以更加的简洁,我们看一下转移方程:

f[new1][j]=f[old][j];if(j>=nums[i-1])    f[new1][j]+=f[old][j-nums[i-1]];

我们可以不必开两层数组,直接在上一层old中计算本层new1的值,
从后往前计算,因为f[old][j-nums[i-1]];我们需要用到的还是old的数据,所以为了不破坏,我们应该使用从后往前算.

class Solution {    public int findTargetSumWays(int[] nums, int target) { if(nums==null||nums.length==0)     return 0; int n=nums.length; //下面是计算出真正的target： int sum=0; for(int i=0;i<n;i++){     sum+=nums[i]; } //特殊情况: if(target>sum||target<-1*sum||(target+sum)%2==1)     return 0; target=(target+sum)/2; int[] f=new int[target+1]; //这里就相当于i=0,前0个数字 //前0个数字组成重量0可以有1种方法 f[0]=1; //前0个数字不可以组成重量i for(int i=1;i<=target;i++){     f[i]=0; } //遍历1~n个数字可以组成的重量 for(int i=1;i<=n;i++){     for(int j=target;j>=0;j--){  if(j>=nums[i-1])      f[j]+=f[j-nums[i-1]];     } } return f[target];    }}