/*
 * Coins.C   -- ECS 122A  CM from   PR
 *
 * Program to count minimum number of US coins 1, 10, 25
 * coins to make change.
 *
 * Shows memoization.
 * 
 *
 */


#include <iostream.h>

const c1 = 1, c2 = 10, c3=25 ;   // Values of the three kinds of coins
const huge = 0x7fffffff;
const maxn = 10000; // Maximum value the program runs on

int min(int a, int b, int c=huge, int d=huge) // 2-4 inputs work
// finds minimum or a,b,c,d
{
 int r = a<b? a:b;
 int s = c<d? c:d;
 return r<s? r:s;
}

int NCoins(int n)   // returns smallest number of coins to make n cents
{
  static mem[maxn+1]; // used to store values computed, 0 = not computed
 if (n==c1 || n==c2 || n==c3 ) return 1;
 if (n<1) return huge;
 if (mem[n]) return mem[n];
 return mem[n]= 1+min(NCoins(n-c1),NCoins(n-c2),NCoins(n-c3));
}

int main()
{
 int cents;

 cout << "How many cents? ";
 cin >> cents;
 if (cents>maxn) exit(1);
 cout << "Can make " << cents << " using " << NCoins(cents) << " coins\n";
 
 return 0;
}