hmm, well now i've implemented it, but it's so damn slow... it should work fast for 100k atleast... here's my implementation:
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MOD 100000
using namespace std;
const int coins[] = {1, 2, 5, 25};
int n, dp[100000][5];
int rec(int n, int m) {
int ret = 0; if(dp[n][m]) return dp[n][m];
if(m == 0 || n == 0) return (dp[n][m] = 1);
if(n < coins[m]) return (rec(n, m-1));
for(int i = 0; i*coins[m] <= n; ++i) {
ret = ((ret%MOD) + (rec(n-i*coins[m], m-1)%MOD))%MOD;
}
return (dp[n][m] = ret);
}
int main( void )
{
scanf("%d", &n);
memset(dp, 0, sizeof dp);
printf("%d\n", rec(n, 3)%MOD);
return 0;
}
i guess my implementation is stupid in some way... or can it run no faster?
Take all of the
% MOD lines out of there. They give you bad results (i.e. there are 43 ways to make 515) and they slow the program down.
Second, it's not an issue here because the smallest "coin" is 1, but this line is a problem if the smallest "coin" is, say, 2:
if(m == 0 || n == 0) return (dp[n][m] = 1);
If
coins[] = {2, 3, 5, 25} or something similar where the smallest element is not 1,
ret (1, 0) would equal 0 (no way to to make 1 from {2, 3, 5, 25}). Thus if this algorithm is meant to cover all
coins arrays, that line would need to change since
dp[n][0] sometimes will equal 0 and sometimes will equal 1 for varying n values. So if you want to allow for that, you'd also need to set the array with memset to some negative number rather than 0 ahead of time if you are checking to see whether the array value has been filled and you allow the smallest coin to be greater than one.
... 
Offline 
Unsolved 
