C ++中的目标总和
假设我们有一个非负整数列表a1，a2，...，an和另一个值，即目标S。现在我们有2个符号+和-。对于每个整数，我们应从+和-中选择一个作为其新符号。我们必须找出几种分配符号的方法，以使整数和与目标值S相同。因此，如果数字为[1,1,1,1,1,1]且S=3，则输出将为5，因为组合是–1+1+1+1+1=3，+1-1+1+1+1=1=3，+1+1-1–1+1+1=3，+1+1+1–1+1=3，+1+1+1+1–1=3。因此，有五种分配方法。
为了解决这个问题，我们将遵循以下步骤-
创建一张大小为21x2001的表dp，并用–1填充。这将用于动态编程方法
递归方法将称为solve()。这将采用pos，数组v，tempSum和实际总和S。这将如下所示：
如果pos与数组v的大小相同，则如果s=tempSum，则返回true，否则返回false
如果dp[pos，tempSum+1000]不为-1，则返回dp[pos，tempSum+1000]
ans：=solve（pos+1，v，tempSum–v[pos]，s）+solve（pos+1，v，tempSum+v[pos]，s）
dp[pos，tempSum+1000]=ans
返回ans
solve()使用参数solve(0,nums,0,s)从主节调用
例子（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int dp[21][2001];
int solve(int pos, vector <int> v, int tempSum, int s){
if(pos == v.size()){
return s == tempSum;
}
if(dp[pos][tempSum+1000]!=-1)return dp[pos][tempSum+1000];
int ans = solve(pos+1,v,tempSum-v[pos],s) +solve(pos+1,v,tempSum+v[pos],s);
dp[pos][tempSum+1000] = ans;
return ans;
}
int findTargetSumWays(vector<int>& nums, int s) {
int n = nums.size();
if(s>1000)return 0;
for(int i =0;i<21;i++){
for(int j =0;j<2001;j++){
dp[i][j] = -1;
}
}
return solve(0,nums,0,s);
}
};
main(){
Solution ob;
vector<int> v = {1,1,1,1,1};
cout << ob.findTargetSumWays(v, 3);
}输入值
[1,1,1,1,1] 3
输出结果
5