uva 357 - Let Me Count The Ways

/*

Problem link

Type: DP - Coin change

*/

 1  #include <iostream>
 2  #include <cstdio>
 3  #include <cstring>
 4  #include <cmath>
 5  #include <cstdlib>
 6  using namespace std;
 7  const int currency[6] = {0,1,5,10,25,50};
 8  const int maxn = 30010;
 9  
10  long long a[maxn][6];
11  int n;
12  
13  int main()
14  {
15      for (int i=0; i<maxn; i++)
16          for (int j=0; j<6; j++) a[i][j] = 0;
17      for (int j=1; j<6; j++) a[0][j] = 1;
18  
19      for (int i=1; i<maxn; i++)
20          for (int j=1; j<6; j++)
21              if (i>=currency[j]) a[i][j] = a[i-currency[j]][j]+a[i][j-1];
22              else a[i][j] = a[i][j-1];
23      while (!cin.eof())
24      {
25          cin >> n;
26          if (cin.eof()) break;
27          long long result = a[n][5];
28          if (result>1)
29              cout << "There are " << result << " ways to produce " << n << " cents change." << endl;
30          else
31              cout << "There is only 1 way to produce " << n << " cents change." << endl;
32      }
33      return 0;
34  }
35