Изменение монет снизу вверх Динамическое программирование

Question

http://uva.onlinejudge.org/external/6/674.html Я пытаюсь решить эту проблему. Тем не менее, обратите внимание, что это не минимальная проблема с обменом монет, а запрашивает различное количество способов заработать N центов, используя монеты 50, 25, 15, 10, 5 и 1 цент. Это довольно просто, поэтому я сделал эту функцию:

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

Также довольно просто добавление динамического программирования с запоминанием:

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

Однако ничего из этого не достаточно быстро - мне нужно динамическое программирование снизу вверх, но у меня возникают трудности с его кодированием, даже с некоторой помощью от 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];
      }
    }
  }
}

Я получаю 0 для каждого результата по какой-то причине, вот мой полный код:

#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

Вы сделали ошибку здесь:

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

Так должно быть DP[i][u]=1 потому что вы можете произвести любое значение i используя 1 центовую монету одним возможным способом. то есть, чтобы взять 5 центов, вы возьмете 5 центовых монет, то есть всего один способ заработать 5 центов.

-----

Кстати, у вас 1-й подход в методе подсчета у вас было это:

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

Или это:

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 (DP[n][m - 1] == -1 || DP[n - s[m]][m] == -1) никогда не сработает, что может быть причиной того, что ваш первый подход слишком медленный: -?