Computer >> Máy Tính >  >> Lập trình >> C ++

Tổng mục tiêu trong C ++

Giả sử chúng ta có một danh sách các số nguyên không âm, a1, a2, ..., an và một giá trị khác, đó là target, S. Bây giờ chúng ta có 2 ký hiệu + và - . Đối với mỗi số nguyên, chúng ta nên chọn một từ + và - làm ký hiệu mới của nó. chúng ta phải tìm xem có bao nhiêu cách gán các ký hiệu để tạo tổng các số nguyên giống với giá trị đích S. Vì vậy, nếu các số là [1,1,1,1,1] và S =3, thì kết quả sẽ là 5, như các kết hợp là - 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. Vậy có năm cách để gán chúng.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Tạo một bảng dp có kích thước 21 x 2001, điền vào bảng này với - 1. Bảng này sẽ được sử dụng cho phương pháp lập trình động
  • Phương thức đệ quy sẽ được sử dụng có tên là giải quyết (). Điều này sẽ lấy pos, array v, tempSum và tổng thực tế S. Điều này sẽ hoạt động như dưới đây -
  • nếu pos bằng với kích thước của mảng v thì trả về true, nếu s =tempSum, ngược lại là false
  • nếu dp [pos, tempSum + 1000] không phải là -1, thì trả về dp [pos, tempSum + 1000]
  • ans:=giải quyết (pos + 1, v, tempSum - v [pos], s) + giải (pos + 1, v, tempSum + v [pos], s)
  • dp [pos, tempSum + 1000] =ans
  • trả lại ans
  • gọi hàm giải quyết () từ phần chính bằng cách sử dụng tham số giải (0, nums, 0, s)

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

#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);
}

Đầu vào 

[1,1,1,1,1]
3

Đầu ra 

5