SHARE
TWEET

coins.cpp

a guest Aug 24th, 2019 76 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.  
  5. const int INF = 1e9;
  6. vector<int> dp;
  7.  
  8. int solve(int m, vector<int> &coins){
  9.     if(m < 0) return INF;
  10.     if(m == 0) return 0;
  11.     if(dp[m] != -1)
  12.         return dp[m];
  13.     int res = INF;
  14.     for(int i = 0; i < coins.size(); i++){
  15.         res = min(res, 1 + solve(m - coins[i], coins));
  16.     }
  17.     return dp[m] = res;
  18. }
  19.  
  20. int minimumNumberCoins(int m, vector<int> &coins){
  21.     dp.assign(m+1, -1);
  22.     int res = solve(m, coins);
  23.     return res == INF ? -1 : res;
  24. }
  25.  
  26. int main(){
  27.     vector<int> v = {5, 10};
  28.     int m = 14;
  29.     int res = minimumNumberCoins(m, v);
  30.     cout << res << '\n';
  31.     return 0;
  32. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top