Still getting wrong output link: https://ide.codingblocks.com/s/176961
Coin change Problem
@Codemaniac_Aditya
hello Auditya,
a) check line no - 24 cin>>coins[m]; should be cin>>coins[i]
b) replace int datatype with long long
c) also u should use 2 dp array to store answer .(dp[n][m])
why 2D array can you please explain!
@Codemaniac_Aditya
ok to resolve you doubt
let me ask you one question.
what is recurrence relation for this problem
f(n,coins,m)=f(n-coins[m-1],coins,m)+f(n,coins,m-1)
Means at first we will consider a case when the mth coin is included and on next it is excluded from the array
great
another question
which parameters are changing when u are calling recursion?
n and length of the array are changing in each call
right…
this is only reason to use 2d dp array (2 parameters are changing).
dp[i][j] will tell u number of ways to make changes of i coins whe.n j is length of coins array.
1 Like
means if there have been 3 changing parameters we had to use 3D dp?
1 Like