สมมติว่าเรามีรายการของจำนวนเต็มที่ไม่ติดลบ, 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 ดังนั้นจึงมีห้าวิธีในการมอบหมาย
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างตาราง dp ขนาด 21 x 2001 หนึ่งตาราง เติมด้วย – 1 ซึ่งจะใช้สำหรับแนวทางการเขียนโปรแกรมแบบไดนามิก
- เมธอดแบบเรียกซ้ำจะเรียกว่า Solve() สิ่งนี้จะใช้ pos, array v, tempSum และผลรวมจริง S ซึ่งจะทำหน้าที่ดังต่อไปนี้ -
- ถ้า pos เท่ากับขนาดของอาร์เรย์ v ให้คืนค่า จริง ถ้า s =tempSum ไม่เช่นนั้น จะเป็นเท็จ
- ถ้า dp[pos, tempSum + 1000] ไม่ใช่ -1 ให้คืนค่า dp[pos, tempSum + 1000]
- ตอบ :=แก้ (pos + 1, v, tempSum – v[pos], s) + แก้ (pos + 1, v, tempSum + v[pos], s)
- dp[pos, tempSum + 1000] =ตอบ
- คืนสินค้า
- เรียก 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
