fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3.  using namespace std;
  4. int matrix(vector<int>coin,ll amount){
  5.  
  6. ll row=coin.size();  //0 to amount
  7. ll col=amount;       // 0 to coins we have
  8.  ll solution[row+1][col+1];
  9.  
  10.   for(ll i=0;i<=row;i++){
  11.   	solution[i][0]=1;   // since with coins greater than>= 0 we able to make 0 amount
  12.   }                        
  13.   for(ll i=1;i<=col;i++){
  14.   	solution[0][i]=0;   // but with 0 coin we only make 0 amount so make all amount ie[0][0] 
  15.   }                      // so make [0][1] to [0][amount]=0;
  16.     for(ll i=1;i<=row;i++){
  17.     	for(ll j=1;j<=col;j++){
  18.     		if(coin[i-1]<=j){     // coins we have less than the amount means we can use it
  19.     			solution[i][j]=solution[i-1][j]+solution[i][j-coin[i-1]];
  20.     		}
  21.     		else{   // else we exclude the coin
  22.     			solution[i][j]=solution[i-1][j];
  23.     		}
  24.     	}
  25.     }
  26.  
  27. cout<<solution[row][col]<<"\n";  //finally return the rightmost corner element in the matrix
  28.                                      // it gives the coins need to get desired amount
  29. return 0;
  30. } 
  31.  
  32.  int main(){
  33.  	vector<int> coin{1,5,10,25,50};
  34.  	ll amount;
  35.  	cin>>amount;
  36.  
  37.  	matrix(coin,amount);
  38.  	return 0;
  39.  }
Runtime error #stdin #stdout 0s 4184KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/i929bQ
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!