Coin Change Problem

#1

I tried solving a different question of this same type where we are told to calculate the total nmber of ways to form a total using a coins array…what is going wrong in my code plz correct it

#2

at line no 24
correct statement will be
int subproblem = solve(arr, n - arr[i], m)+1;
you also have to add 1

#3

Still getting wrong answer…answer should be 4 i am getting 14

#4

for which input you are trying?

#5

N=4
arr={1,2,3}
this is my input

#6

POssible ways can be 1111 22 13 112

#7

This question is just a variation of the question shown in videos right so the logic is correct no?

#8

actually the problem is
first you set dp[0]=1 and then you use menset to set all values=0

so dp[0]=1 should be used later

#9

I made some changes…but no luck…

#10

this will not work
previous one is better
but there is also problem with that
it is considering the reduntant case also
for example for n=4
it is considering
1 1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1

as you can see there is repetation
so this approach is not correct

#11

this is correct way to do this
using memoization
you have to make 2D array

#12

I am a bit confused about how to decide m and n as column or row if i would have taken n as columns and m as rows would the answer differ?

#13

Can u please explain ur intuition for choosing rows and columns

#14

no there will be no problem
why should ans differ?
you are storing the ans of m,n at dp[m][n] and using it when required
if you use dp[n][m] then also you can use it

#15

okay understood Thank you

#16

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.