dynamic-programming - 目标总和 [leetcode] 通过分配符号计算具有给定目标总和的子集

Question

class Solution {
public:
    
    int solve(vector<int>& v, int n , int s ,vector<vector<int>>& dp){
        
        if(s == 0 ){
            return 1;
        }
        if(n == 0){
            return 0;
        }
        if(dp[n -1][s] != -1) return dp[n - 1][s];
        
        if(v[n - 1] == 0){
           return dp[n][s] = solve(v,n-1,s,dp);
        }
        else if(v[n-1] <= s)
        return dp[n][s] = (solve(v,n-1 , s, dp )  + solve(v, n-1, s - v[n - 1],dp));
        else
        return dp[n][s] = solve(v,n-1,s,dp);
       
        
    }
    
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        int n = nums.size();
        for(int i= 0 ;i<n;i ++ ){
            sum += nums[i];
        }
         
        if(S > sum ) return 0;
        if(-S < -sum) return 0;
        int asum;
        if((sum + S)%2 == 0)
            asum = (sum + S)/2;
        else{
            return 0;
        }
        
        
            int c= 0 ;
            for(int i = 0 ; i < n ;i++){
                if(nums[i] == 0 ){
                    c += 1;
                }
            }
            
        
        vector<vector<int>> dp(n + 1 , vector<int>(asum  +   1)) ;
        for(int i = 0 ; i < n  +1;i++){
            for(int j = 0 ; j < asum  + 1; j++ ){
                dp[i][j] = -1;
            }
        }
        int res = solve(nums ,n, asum , dp);
      //  cout<<dp[0][0]<<" "<<dp[2][3]<<endl;
        return res*pow(2, c);
             
        
        
    }
};

失败的测试用例：

[9,7,0,3,9,8,6,5,7,6]
2

我不知道我的dp哪里错了

我实现了这个：

如果你分配 + 或 -ve 基本上你将给定的数组划分为集合并找到那里总和的差异

所以问题减少到 s1 - s2 = 现在的目标总和 s2 = totalsum - s1 所以，

s1 = (targetsum + totalsum)/2;

并且极端情况是处理零 int it 。

但它失败了。

标签： dynamic-programmingknapsack-problem

Answer 1

好的，我得到了我错的解决方案：

if(dp[n -1][s] != -1) 返回 dp[n - 1][s]; // 这里我在寻找 dp[n -1] 而不是 dp[n] 。所以，我纠正了它，它最终被接受了。

这里是整个代码。

int solve(vector<int>& v, int n , int s ,vector<vector<int>>& dp){
    
    if(s == 0)
        return 1;
    
    if(n == 0)
        return 0;
    
    if(dp[n][s] != -1)
        return dp[n][s];
    
    if(v[n - 1] == 0)
       return dp[n][s] = solve(v,n-1,s,dp);  
    else if(v[n-1] <= s)
       return dp[n][s] = (solve(v,n-1 , s, dp )  + solve(v, n-1, s - v[n - 1],dp));
    else
       return dp[n][s] = solve(v,n-1,s,dp);
   
    
}

int findTargetSumWays(vector<int>& nums, int S) {
    int sum = 0;
    int n = nums.size();

    for(int i= 0 ;i<n;i ++ ){
        sum += nums[i];   // total sum
    }
     
    if(S > sum ) return 0;
    if(-S < -sum) return 0;

    int asum;   // actual sum required

    if((sum + S)%2 == 0)
        asum = (sum + S)/2;
    else{
        return 0;
    }
    
    // count no of zeroes
    int c= 0 ;
    for(int i = 0 ; i < n ;i++){
        if(nums[i] == 0 ){
             c += 1;
        }
    }
        
    
    vector<vector<int>> dp(n + 1 , vector<int>(asum  +   1)) ;
    for(int i = 0 ; i < n  +1;i++){
        for(int j = 0 ; j < asum  + 1; j++ ){
            dp[i][j] = -1;
        }
    }

    int res = solve(nums ,n ,asum,dp);
    return res*pow(2, c);
         
    
    
}