Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /////// coin change by matrix// un finished
- #include<bits/stdc++.h>
- using namespace std;
- #define scInt(x) scanf("%d",&x)
- int dp[1000][1000];
- vector<int > coins;
- int start;
- int samne_jabo_koi_ghor;
- int coinChange(int am)
- {
- int i,j;
- if(dp[coins[coins.size()-1]][am])
- return dp[coins[coins.size()-1]][am];
- for(i=0; i<coins.size(); i++)
- {
- for(j=0; j<=am; j++)
- {
- if(j==0)
- {
- dp[coins[i]][j]=1;
- printf(" dp[%d][%d]=%d \n",coins[i],j,dp[coins[i]][j]);
- continue;
- }
- else if(coins[i]==0)
- {
- dp[coins[i]][j]=0;
- printf(" dp[%d][%d]=%d \n",coins[i],j,dp[coins[i]][j]);
- continue;
- }
- if(coins[i]<j){
- dp[coins[i]][j]= dp[coins[i-1]][j] ;
- printf(" dp[%d][%d]=%d \n",coins[i],j,dp[coins[i-1]][j]);
- continue;
- }
- else if(coins[i]==j){
- dp[coins[i]][j]= dp[coins[i-1]][j]+1 ;
- samne_jabo_koi_ghor=j;
- printf(" dp[%d][%d]=%d \n",coins[i],j,dp[coins[i-1]][j]);
- continue;
- }
- dp[coins[i]][j]= dp[coins[i-1]][j]+dp[coins[i]][j-samne_jabo_koi_ghor] ;
- }
- }
- return dp[coins[coins.size()-1]][am];
- }
- int main()
- {
- start=0;
- int n,r,i,tem,amount;
- puts ("enter number of coins the coins");
- scInt(n);
- coins.push_back(0);
- for(i=1; i<=n; i++)
- {
- scInt(tem);
- coins.push_back(tem);
- }
- scInt(amount);
- printf("ways to have %d: %d\n",amount ,coinChange(amount));
- while(scInt(amount)!=EOF){
- puts ("\n\nenter amount");
- printf("ways to have %d: %d\n",amount ,coinChange(amount));
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement