Advertisement
spider68

coin change problem total way

Mar 21st, 2020 (edited)
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.67 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int main() {
  5.     int i,j,t,n,x;
  6.     cin>>t;
  7.     while(t--)
  8.     {
  9.         cin>>n;
  10.         int coin[n];
  11.         for(i=0;i<n;i++)cin>>coin[i];
  12.         int w;
  13.         cin>>w;
  14.         int a[n][w+1];
  15.         for(i=0;i<n;i++)
  16.         {
  17.             for(j=0;j<=w;j++)
  18.             {
  19.                 if(j==0){a[i][j]=1;continue;}
  20.                 if(i==0){if(j%coin[i]==0)a[i][j]=1;
  21.                     else a[i][j]=0;
  22.                 }
  23.                 else{
  24.                     if(coin[i]>j)a[i][j]=a[i-1][j];
  25.                     else{
  26.                         a[i][j]=a[i-1][j]+a[i][j-coin[i]];
  27.                     }
  28.                 }
  29.             }
  30.         }
  31.         cout<<a[i-1][j-1]<<endl;
  32.     }
  33.     return 0;
  34. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement