Niloy007

Coin Change

Mar 24th, 2021
545
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int bestNumCoins[1000000];
  5.  
  6. int DPChange(int M, int c[], int d) {
  7.     bestNumCoins[0] = 0;
  8.     for (int m = 1; m <= M; m++) {
  9.         bestNumCoins[m] = INT_MAX;
  10.         for (int i = 0; i < d; i++) {
  11.             if (m >= c[i]) {
  12.                 if (bestNumCoins[m - c[i]] + 1 < bestNumCoins[m]) {
  13.                     bestNumCoins[m] = bestNumCoins[m - c[i]] + 1;
  14.                 }
  15.             }
  16.         }
  17.     }
  18.     return bestNumCoins[M];
  19. }
  20.  
  21. int main() {
  22.     int M, d;
  23.     cin >> M >> d;
  24.     int c[d];
  25.     for (int i = 0; i < d; i++) {
  26.         cin >> c[i];
  27.     }
  28.    
  29.     int ans = DPChange(M, c, d);
  30.    
  31.     cout << ans << endl;
  32. }
RAW Paste Data