Coin Change Bottom Up Dynamic Programming

Question

http://uva.onlinejudge.org/external/6/674.html I'm trying to solve that problem. Note, though, that it's not the minimum coin change problem, it asks me for the different number of ways to make N cents using 50, 25, 15, 10, 5 and 1 cent coins. It's fairly straightforward, so I made this function:

int count(int n, int m) // n is the N of the problem, m is the number of coin types and s[] is {1, 5, 10, 25, 50}
{
  if (n == 0)
  {
    return 1;
  }

  if (n < 0)
  {
    return 0;
  }

  if (m < 0 && n >= 1)
  {
    return 0;
  }

  return DP[n][m - 1] + DP[n - s[m]][m];
}

Fairly straightforward too is adding Dynamic Programming with memoization:

int count(int n, int m)
{
  if (n == 0)
  {
    return 1;
  }

  if (n < 0)
  {
    return 0;
  }

  if (m < 0 && n >= 1)
  {
    return 0;
  }

  if (DP[n][m - 1] == -1 || DP[n - s[m]][m] == -1)
  {
    return count(n, m - 1) + count(n - s[m], m);
  }
  else
  {
    return DP[n][m - 1] + DP[n - s[m]][m];
  }
}

However, none of these is fast enough - I need bottom up Dynamic Programming, but I am having difficulties coding it, even with some help from Algorithmist - http://www.algorithmist.com/index.php/Coin_Change.

void generate()
{
  for (i = 0; i < MAX; i++)
  {
    for (u = 0; u < m; u++)
    {
      if (i == 0)
      {
        DP[i][u] = 1;
      }
      else if (u == 0)
      {
        DP[i][u] = 0;
      }
      else if (s[u] > i)
      {
        DP[i][u] = DP[i][u - 1];
      }
      else
      {
        DP[i][u] = DP[i][u - 1] + DP[i - s[u]][u];
      }
    }
  }
}

I get 0 for every result for some reason, here's my full code:

#include <stdio.h>
#include <string.h>

using namespace std;

#define MAX 7490

int s[] = {1, 5, 10, 25, 50}, m = 5, input, DP[MAX][5], i, u;

int count(int n, int m)
{
  if (n == 0)
  {
    return 1;
  }

  if (n < 0)
  {
    return 0;
  }

  if (m < 0 && n >= 1)
  {
    return 0;
  }

  if (DP[n][m - 1] == -1 || DP[n - s[m]][m] == -1)
  {
    return count(n, m - 1) + count(n - s[m], m);
  }
  else
  {
    return DP[n][m - 1] + DP[n - s[m]][m];
  }
}

void generate()
{
  for (i = 0; i < MAX; i++)
  {
    for (u = 0; u < m; u++)
    {
      if (i == 0)
      {
        DP[i][u] = 1;
      }
      else if (u == 0)
      {
        DP[i][u] = 0;
      }
      else if (s[u] > i)
      {
        DP[i][u] = DP[i][u - 1];
      }
      else
      {
        DP[i][u] = DP[i][u - 1] + DP[i - s[u]][u];
      }
    }
  }
}

int main()
{
  memset(DP, -1, sizeof DP);
  generate();

  while (scanf("%d", &input) != EOF)
  {
    //printf("%d\n", count(input, 4));
    printf("%d\n", DP[input][4]);
  }

  return 0;
}

Answer 1

You did the mistake here:

else if (u == 0)
{
   DP[i][u] = 0;
}

It should be DP[i][u]=1 because you can produce any value i using 1 cent coin in 1 possible way. i.e. to take 5 cent you will take 5 one cent coins which is one way to make 5-cent in total.

-----

Btw, in you 1st approach in count method did you have this:

if (DP[n][m - 1] == -1 || DP[n - s[m]][m] == -1)
{
  return count(n, m - 1) + count(n - s[m], m);
}

Or this:

if (DP[n][m - 1] == -1 || DP[n - s[m]][m] == -1)
{
    return DP[n][m] = count(n, m - 1) + count(n - s[m], m);
}

If you did not memoize an already calculated result then this memoization check if (DP[n][m - 1] == -1 || DP[n - s[m]][m] == -1) will never work, which might be the cause of your 1st approach to be too slow :-?