Sajib_Ahmed

DP coin change

Jul 31st, 2019
203
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.53 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     int n,i,l;
  6.     cin>>n>>l;
  7.     int a[l],c[n];
  8.     for(i=0; i<l; i++)
  9.     {
  10.         cin>>a[i];
  11.     }
  12.     c[0]=0;
  13.     int j;
  14.     for(j=1; j<=n; j++)
  15.     {
  16.         int mi=9999999;
  17.         for(i=0; i<l; i++)
  18.         {
  19.             if(a[i]<=j)
  20.             {
  21.                 if((1+c[j-a[i]])<mi)
  22.                 {
  23.                     mi=(1+c[j-a[i]]);
  24.                 }
  25.             }
  26.         }
  27.         c[j]=mi;
  28.  
  29.     }
  30.  
  31.  
  32.     cout<<c[n]<<" "<<endl;
  33.  
  34. }
Add Comment
Please, Sign In to add comment