Advertisement
naeem043

C DP Coin Change

Jul 20th, 2018
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 0.79 KB | None | 0 0
  1. #include<stdio.h>
  2. int c[5], amn = 67, dp[6][100],seq[10000],count=0,m=0,sum=0;
  3.  
  4. int make(int i,int amount)
  5. {
  6.     if(i>=5)
  7.     {
  8.         if(amount == 0) return 1;
  9.         else return 0;
  10.     }
  11.     if(dp[i][amount] != -1) return dp[i][amount];
  12.     int ret1 = 0,ret2 = 0;
  13.     if(amount-c[i]>=0) ret1 = make(i,amount-c[i]);
  14.  
  15.      ret2 = make(i+1,amount);
  16.  
  17.     return (dp[i][amount] = ret1 + ret2);
  18.  
  19. }
  20.  
  21. int main()
  22. {
  23.     int j,i;
  24.  
  25.     c[0] = 1;
  26.     c[1] = 2;
  27.     c[2] = 5;
  28.     c[3] = 10;
  29.     c[4] = 20;
  30.  
  31.     for(i=0;i<6;i++)
  32.     {
  33.         for(j=0;j<2005;j++)
  34.         {
  35.             dp[i][j] = -1;
  36.          }
  37.     }
  38.      printf("%d",make(0,amn));
  39.      printf("\nTotal coin :%d\n",count);
  40.      printf("\Sum :%d\n",sum);
  41.      for(i=0;i<6;i++) printf("%d ",seq[i]);
  42.  
  43.     return 0;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement