Đổi xu 2 trong C ++

Giả sử chúng ta có tiền xu có mệnh giá khác nhau và tổng số tiền. chúng ta phải Viết một mô-đun để tính toán số lượng kết hợp tạo nên số tiền đó. chúng ta có thể giả định rằng chúng ta có vô số loại đồng xu. Vì vậy, nếu số tiền là 5 và tiền xu là [1, 2, 5], thì có bốn kết hợp. (1 + 1 + 1 + 1 + 1), (1 + 1 + 1 + 2), (1 + 2 + 2), (5)

Để 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 mảng dp có kích thước số tiền là + 1
• dp [0]:=1
• n:=kích thước của mảng tiền xu
• cho tôi trong phạm vi từ 0 đến n - 1
  • cho j trong số tiền xu [i] thành số tiền
    • dp [j]:=dp [j - xu [i]]
• trả lại dp [số tiền]

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 change(int amount, vector<int>& coins) {
      vector <int> dp(amount + 1);
      dp[0] = 1;
      int n = coins.size();
      for(int i = 0; i < n; i++){
         for(int j = coins[i]; j <= amount; j++){
            dp[j] += dp[j - coins[i]];
         }
      }
      return dp[amount];
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,5};
   cout << (ob.change(5, v));
}

Đầu vào

5
[1,2,5]

Đầu ra

4