In the coin change problem

#1

The recursion isnt working.Will 1d array do?
Or I need to use 2d array?

#2

@Babin
hello Babin,
first try to solve it using 2d array after that u can optimise ur space complexity to linear.

checkout this link for both the approaches - > https://www.geeksforgeeks.org/coin-change-dp-7/

#3

int coins2(int arr[],int sum,int n)
{
if(n<=0)
return 0;
if(sum<0)
return 0;
int c[sum+1][n];
/* for(int i=0;i<n;i++)
{
c[0][i]=0;
}*/
memset(c[0],1,sizeof(c[0]));
for(int i=1;i<=sum;i++)
{
for(int k=0;k<n;k++)
{
if(arr[k]<=i)
c[i][k]=c[i][k-1]+c[i-arr[k]][k];
else
c[i][k]=c[i][k-1];
}
}
return c[sum][n-1];

}
Why is the code wrong?

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.