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。因此，有五种分配方法。

为了解决这个问题，我们将遵循以下步骤-

• 创建一张大小为21 x 2001的表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