674 - Coin Change

[Shahidul.CSE]

Do you need to reset preCal at every test case?

Yes, I myself also thought that I don't need to reset preCal at every test case. And when I tried without reset preCal at every test case, it gave wrong outputs. So then, when reset preCal at every test case, it gives correct outputs, but got TLE.

For example, if I don't reset preCal at every test case, for the input bellow it gives the same output for every test case:

Code: Select all

    0
    57
    129
    134
    239
    277
    300
    386
    393
    455
    510
    535
    568
    610
    637
    642
    790
    1426
    1446
    1498
    1503
    1590
    1600
    1624
    1635
    1647
    1691
    1722
    1931
    2116
    2261
    2455
    2547
    2663
    2703
    2707
    2765
    2827
    2915
    3258
    3349
    3915
    3960
    4261
    4691
    4800
    4862
    4928
    5001
    5151
    5246
    5331
    5376
    5559
    5826
    5853
    5975
    6071
    6168
    6239
    6321
    6423
    6482
    6543
    6620
    6796
    6962
    6973
    7026
    7104
    7355
    7414
    7481
    7489

program gave output

Code: Select all

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

But when reset preCal at every case, it gives correct outputs.
So, what to do?

[brianfry713]

Rewrite your code.
Precompute the results for all possible inputs.
http://www.geeksforgeeks.org/dynamic-pr ... in-change/

[messiNayan]

Getting Wrong answer:Help me
#include<stdio.h>
#include<string.h>


int coins[] = { 50, 25, 10, 5, 1 };
int dp[6][7490];
int makeAmount(int i, int amount);
int main(void)
{
int amount;
memset(dp, -1, sizeof(dp)); //
while(1)// (scanf("%d", &amount) != EOF)
{
scanf("%d", &amount);
printf("%d\n", makeAmount(0, amount));
}

return 0;
}

int makeAmount(int i, int amount)
{
if (dp[amount] != -1)
return dp[amount];

int ret1 = 0, ret2 = 0;

if (i >= 5)
{
if (amount == 0)
return 1;
else
return 0;
}

if (amount - coins >= 0)
ret1 = makeAmount(i, (amount - coins));
ret2 = makeAmount((i + 1), amount);
return (dp[amount] = (ret1 + ret2));
}