欧酷网

您的位置:主页>算法>

LeetCode--494.目标和

494.目标和–点击查看题目要求


解法一:枚举法,根据递归一一列举
不过此方法太耗时,时间复杂度为o(2^N)

class Solution {
   
	  int count = 0;
	  public int findTargetSumWays(int[] nums, int S) {
		
		     calculate(nums, 0, 0, S);
		     return count;

	        
	    }
	  
	  public void calculate(int[] nums,int i,int sum,int S) {
		  if(i==nums.length) {
			  if(sum==S)count++;
		  }else {
			  calculate(nums,i+1,sum+nums[i],S);
			  calculate(nums,i+1,sum-nums[i],S);
		  }
	  }}

解法二:动态规划
令dp[i][j]表示nums[i]和为j的可能情况
因为二维数组中j一般为正数,所以要加上1000
dp[0][+nums[0]+1000]=1;
dp[0][-nums[0]+1000]+=1;//是为了防止nums[0]=0的情况
递推公式:
dp[i][j+nums[i]]+=dp[i-1][j];
dp[i][j-nums[i]]+=dp[i-1][j];
//+=是因为可能有多条路径=dp[i][j+nums[i]],dp[i][j-nums[i]]
此方法
时间复杂度为:NSum
空间复杂度为:N
Sum

class Solution {
       public int findTargetSumWays(int[] nums, int S) {
    	
    	int[][] dp = new int[nums.length][2001];
    	dp[0][+nums[0]+1000]=1;
    	dp[0][-nums[0]+1000]+=1;
    	for(int i=1;i<nums.length;i++) {
    		for(int sum=-1000;sum<=1000;sum++) {
    			if(dp[i-1][sum+1000]>0) {
    				dp[i][sum+1000+nums[i]]+=dp[i-1][sum+1000];
    				dp[i][sum+1000-nums[i]]+=dp[i-1][sum+1000];
    			}
    		}
    	}
    	
    	return S > 1000 ? 0 : dp[nums.length-1][S+1000];
    	
        
    }}

解法三: 动态规划+空间优化
我们可以优化空间复杂度,用两个一维数组
时间复杂度:N*sum
空间复杂度:sum

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
    	
    	int[] dp = new int[2001];
    	dp[+nums[0]+1000]=1;
    	dp[-nums[0]+1000]+=1;
    	
    	for(int i=1;i<nums.length;i++) {
    		int[] next = new int[2001];
    		for(int sum=-1000;sum<=1000;sum++) {
    			if(dp[sum+1000]>0) {
    				next[sum+1000+nums[i]]+=dp[sum+1000];
    				next[sum+1000-nums[i]]+=dp[sum+1000];
    			}
    		}
    		dp=next;
    	}
    	return S > 1000 ? 0 : dp[S+1000];
        
    }}

相关文章推荐