資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告