#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>

/**
 * Determines the min number of stamps needed for n cents total with
 * 1, 23, and 37 cent stamps (it is 2002).
 *
 * @param n a nonnegative integer
 */
int stamps_rec(int n);
int stamps_dp(int n);

int min2(int x, int y);
int min3(int x, int y, int z);

int main(int argc, char **argv)
{
  if (argc < 2 || strlen(argv[1]) == 0 || !isdigit(argv[1][0]))
    {
      fprintf(stderr, "USAGE: %s n\n", argv[0]);
      return 1;
    }

  int n = atoi(argv[1]);
  
  printf("min(%d) = %d\n", n, stamps_rec(n));
}

int stamps_rec(int n)
{
  if (n == 0)
    {
      return 0;
    }
  else if (n < 23)
    {
      return 1 + stamps_rec(n - 1);
    }
  else if (n < 37)
    {
      return 1 + min2(stamps_rec(n - 1), stamps_rec(n - 23));
    }
  else
    {
      return 1 + min3(stamps_rec(n - 1), stamps_rec(n - 23), stamps_rec(n - 37));
    }
}

int min2(int x, int y)
{
  return x < y ? x : y;
}

int min3(int x, int y, int z)
{
  return min2(min2(x, y), z);
}

int stamps_dp(int n)
{
  int fewest[n + 1];
  int denominations[] = {1, 22, 37};
  
  fewest[0] = 0;

  for (int i = 1; i <= n; i++)
    {
      int min = i;
      for (int j = 0; j < 3; j++)
	{
	  if (denominations[j] <= i && fewest[i - denominations[j]] < min)
	    {
	      min = fewest[i - denominations[j]];
	    }
	}
      fewest[i] = 1 + min;
    }
  return fewest[n];
}