目标和[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或-ve，基本上你就是把给定的数组划分成一组，并找到求和的diff

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

s1 = (targetsum + totalsum)/2;

角落的情况是处理零。

但它失败了。

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);



}

Answer 2

不确定你的bug，你必须使用调试器。

然而，这也是一种类似的动态编程方法，并且会被接受：

#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];
}
};

---

参考文献

• 有关更多详细信息，请参阅讨论板。有很多公认的解决方案，包括各种语言和解释，有效的算法，以及渐近时间/空间复杂性分析^1，2