加减的目标值
给定一个正整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ,然后串联起所有整数,可以构造一个 表达式 :
例如,nums = [2, 1] ,可以在 2 之前添加 '+' ,在 1 之前添加 '-' ,然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
链接
WA:暴力题解
果然暴力就是超时
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int n=nums.size();
vector<int>temp,t;
for(int i=0;i<n;i++){
if(i==0){
temp.push_back(nums[i]);
temp.push_back(-nums[i]);
}else{
for(auto num:temp){
t.push_back(num+nums[i]);
t.push_back(num-nums[i]);
}
temp=t;
t.clear();
}
}
int ans=0;
for(auto num:temp){
if(num==target){
ans++;
}
}
return ans;
}
};
AC:DP题解
思路:sum来判断走到每一个nums下标的边界值[-sum,sum],然后计算走到当前的nums[i]需要几步
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int n=nums.size();
vector<vector<int> >dp(n,vector<int>(40001,0));
int add=20000;
//初始化
dp[0][add+nums[0]]=1;
dp[0][add-nums[0]]++;//这里要注意如果nums[0]==0,则不可以用简单的赋值语句dp[0][add-nums[0]]=1
//dp
int sum=0;
sum+=nums[0];
for(int i=1;i<n;i++){
sum+=nums[i];
for(int j=-sum;j<=sum;j++){
dp[i][j+add]=dp[i-1][j-nums[i]+add]+dp[i-1][j+nums[i]+add];
}
}
return dp[n-1][target+add];
}
};
官方题解
DFS
可能是因为nums的长度为20,所以时间复杂度\(O(2^n)\)可以接受
DFS解法如下:
class Solution {
public:
int count = 0;
int n;
int t;
void dfs(int index,int sum,vector<int>&nums){
if(index<n){
dfs(index+1,sum+nums[index],nums);
dfs(index+1,sum-nums[index],nums);
}else if(index==n&&sum==t){
count++;
}
}
int findTargetSumWays(vector<int>& nums, int target){
n=nums.size();
t=target;
dfs(0,0,nums);
return count;
}
};
标签:专项,target,nums,int,sum,vector,dp,Leetcode,DP
From: https://www.cnblogs.com/SaltyCheese/p/17278885.html