数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的目标和
假设我们有一系列非负整数，a1、a2、...、an，以及另一个值，即目标值 S。现在我们有 2 个符号 + 和 -。对于每个整数，我们应该从 + 和 - 中选择一个作为其新的符号。我们必须找出有多少种方法可以分配符号，使整数的总和等于目标值 S。因此，如果数字是 [1,1,1,1,1]，而 S = 3，则输出将为 5，因为组合为 – 1 + 1 + 1 + 1 + 1 = 3，+ 1 – 1 + 1 + 1 + 1 = 3，+ 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 的大小相同，则返回 true，如果 s = tempSum，否则返回 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(0, nums, 0, s) 调用 solve()
示例（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
更新于: 2020-04-29
617 次查看
广告