fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int coins[100];
  4. int amount,n;
  5. int dp[100][1000];
  6. int Coin_Change_Iter(int i,int amount)
  7. {
  8. for(int j=0;j<=amount;j++)
  9. {
  10. dp[n][j]=1000000000;
  11. }
  12. for(int i=0;i<=n;i++)
  13. {
  14. dp[i][0]=0;
  15. }
  16. for(int i=n-1;i>=0;i--)
  17. {
  18. for(int j=1;j<=amount;j++)
  19. {
  20. if(j>=coins[i])
  21. {
  22. dp[i][j]=min(1+dp[i+1][j-coins[i]],dp[i+1][j]);
  23. }
  24. else
  25. {
  26. dp[i][j]=dp[i+1][j];
  27. }
  28. }
  29. }
  30. return dp[0][amount];
  31. }
  32.  
  33. int main()
  34. {
  35. cin>>n;
  36. for(int i=0;i<n;i++)
  37. {
  38. cin>>coins[i];
  39. }
  40. cin>>amount;
  41.  
  42. int min_coins_Iter=Coin_Change_Iter(0,amount);
  43. cout<<min_coins_Iter<<endl;
  44. }
  45.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
7
2 3 5 6 9 12 15
9
stdout
copy 
1
https://ideone.com/vOfQ2i
language:
C++ (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!