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

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