Advertisement
Rezaur_Rahman

Coin Change DP - Number of Ways

Aug 17th, 2019
127
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 0.80 KB | None | 0 0
  1. #include<stdio.h>
  2.  
  3. int n,tk,arr[100];
  4.  
  5. int coinChange();
  6.  
  7. int main()
  8. {
  9.     printf("Number of coin type: ");
  10.     scanf("%d",&n);
  11.     int i;
  12.     printf("Enter them one by one:\n");
  13.     for(i=0;i<n;i++)
  14.         scanf("%d",&arr[i]);
  15.     printf("Amount you want to make using the coins: ");
  16.     scanf("%d",&tk);
  17.  
  18.     int ans=0;
  19.     ans=coinChange();
  20.     printf("Ans: %d\n",ans);
  21.  
  22.     return 0;
  23. }
  24.  
  25. int coinChange()
  26. {
  27.     int i,j,x,y;
  28.     int TB[tk+1][n];
  29.  
  30.     for(i=0;i<n;i++)
  31.         TB[0][i]=1;
  32.  
  33.     for(i=1;i<=tk;i++)
  34.         for(j=0;j<n;j++)
  35.         {
  36.             if((i-arr[j])>=0)
  37.                 x=TB[i-arr[j]][j];
  38.             else x=0;
  39.  
  40.             if(j>=1)
  41.                 y=TB[i][j-1];
  42.             else y=0;
  43.  
  44.             TB[i][j]=x+y;
  45.         }
  46.  
  47.     return TB[tk][n-1];
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement