Coin change problem --why not??

Revision en1, by mkmeden, 2022-07-13 21:32:29

In the standard coin exchange problem were each denominations are available infinite times and we need to find the number of ways in which we can form the target value :

for a recursive function int fun(int n , int val) and the arr contains the denominations. ``` int not_take = fun(n-1 , val) int take = fun(n ,val — arr[n])

this is how the possible cases for the recursive calls should be .

But I thought it like this instead ( definitely wrong ) 

int not_take = fun(n-1 , val) int take = fun(n ,val — arr[n]) + fun(n-1 , val — arr[n])

```

I considered one more case too were we take the coin and move to the next index and I cant find a reasoning why this is wrong logically .

Might be a stupid doubt but cant get over it just like that. Can anyone tell me why is it wrong to consider that case.

Thanks

Tags dynamic programming

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English mkmeden 2022-07-13 21:36:53 26
en3 English mkmeden 2022-07-13 21:35:10 6
en2 English mkmeden 2022-07-13 21:34:07 221
en1 English mkmeden 2022-07-13 21:32:29 895 Initial revision (published)