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

int stamps_dp(int n, int v[], int k);
int stamps_memo(int n, int v[], int k);
int stamps_rec(int n, int v[], int k);

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]);

  int value[] = {1, 23, 37};
  int k = 3;
  
  printf("stamps(%d) = %ld\n", n, stamps_memo(n, value, 3));
  printf("stamps(%d) = %ld\n", n, stamps_dp(n, value, 3));
  printf("stamps(%d) = %ld\n", n, stamps_rec(n, value, 3));
}

int stamps_rec(int n, int v[], int k)
{
  if (n < 0)
    {
      return INT_MAX; // for "can't be done"
    }
  else if (n == 0)
    {
      return 0;
    }
  else
    {
      int min = INT_MAX;
      for (int i = 0; i < k; i++)
	{
	  int m = stamps_rec(n - v[i], v, k);
	  if (m < min)
	    {
	      min = m;
	    }
	}
      
      if (min != INT_MAX) // be careful about overflow!
	{
	  return min + 1;
	}
      else
	{
	  return INT_MAX;
	}
    }
}

int stamps_memo_helper(int n, int v[], int k, int memo[]);

int stamps_memo(int n, int v[], int k)
{
  // initialize memo to empty (-1 since numbers of stamps always non-negative)
  int memo[n + 1];
  for (int i = 0; i <= n; i++)
    {
      memo[i] = -1;
    }

  // initialize base case
  memo[0] = 0;

  // call memoized recursive function
  return stamps_memo_helper(n, v, k, memo);
}

int stamps_memo_helper(int n, int v[], int k, int memo[])
{
  if (n < 0)
    {
      // negative values can't be done
      return INT_MAX;
    }
  else if (memo[n] != -1)
    {
      // value is already in the memo
      return memo[n];
    }
  else
    {
      // same as recursive version, except...
      int min = INT_MAX;
      for (int i = 0; i < k; i++)
	{
	  int m = stamps_memo_helper(n - v[i], v, k, memo);
	  if (m < min)
	    {
	      min = m;
	    }
	}

      // ...save value in memo...
      if (min != INT_MAX)
	{
	  memo[n] =  min + 1;
	}
      else
	{
	  memo[n] = INT_MAX;
	}

      // ...before returning it
      return memo[n];
    }
}

int stamps_dp(int n, int v[], int k)
{
  // initialize memo with base case
  int memo[n + 1];
  memo[0] = 0;

  // fill out other entries in memo
  for (int i = 1; i <= n; i++)
    {
      // apply recurrence, but instead of recursion, get results directly from memo
      int min = INT_MAX;
      for (int j = 0; j < k; j++)
	{
	  if (i - v[j] >= 0 && memo[i - v[j]] < min)
	    {
	      min = memo[i - v[j]];
	    }
	}
      if (min != INT_MAX)
	{
	  memo[i] = min + 1;
	}
      else
	{
	  memo[i] = INT_MAX;
	}
    }

  // return entry in memo we're interested in
  return memo[n];
}