заданная сумма [leetcode] подсчет подмножества с заданной целевой суммой путем присвоения знаков - PullRequest
Новая
       77

заданная сумма [leetcode] подсчет подмножества с заданной целевой суммой путем присвоения знаков

0 голосов
/ 10 июля 2020 
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 неправильный

Я реализовал это:

если вы назначаете + или -в основном вы делите данный массив на множество и находите разницу в сумме

, поэтому проблема сводится к s1 - s2 = target sum now s2 = totalsum - s1, поэтому 

s1 = (targetsum + totalsum)/2;

а в угловом случае нужно обрабатывать нули в нем.

но это не удается.

Ответы [ 2 ]

1 голос
/ 10 июля 2020

Не уверен в своей ошибке, для этого вам придется использовать отладчик.

Однако это аналогично подходу к программированию на динамике c и будет принято: 

#include <vector>
#include <numeric>

struct Solution {
    static const inline int findTargetSumWays(const std::vector<int> &nums, const int target) {
        int copy_target = target;
        std::vector<int> copy_nums = nums;
        int sum = std::accumulate(copy_nums.begin(), copy_nums.end(), 0);

        if (sum < copy_target || (sum + copy_target) & 1) {
            return 0;
        }

        return get_subarray_sum(copy_nums, (sum + copy_target) >> 1);

    }

private:
    static const inline int get_subarray_sum(const std::vector<int> &nums, const int target) {
        std::vector<int> symbols_assign(target + 1, 0);
        symbols_assign[0] = 1;

        for (const auto &num : nums)
            for (int index = target; index > num - 1; index--) {
                symbols_assign[index] += symbols_assign[index - num];
            }

        return symbols_assign[target];
    }
};

Ссылки

0 голосов
/ 11 июля 2020

хорошо, я получил решение, в котором ошибался:

if (dp [n -1] [s]! = -1) return 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);
         
    
    
}
...