Easy dynamic programming

the problem is about coin change - "how many ways you can change 3,5,10 dollars if you have 5c,10c ......the problem is solved many times on various blogs( solution )



In dp, the hardest thing is to understand the relation between subproblems and get the formula(optimal substructure)




I only give the actual for loop that stores the ways into 2d table like the solution:



for (int i = 2; i = coins[i]) n[i][m] = n[i-1][m] + n[i][m - coins[i]]; else n[i][m] = n[i-1][m];**



My thinking.



for example: (else case)



* I have the amount 5 cents and 1 coin to use : 5c. there is only 1 way : 5c = 1 * 5c (store n[5][coin(5)])

* I have the amount 5c and 2 coins to use : 5c and 10c i can't use BOTH 5C and 10c => i go back to 1 WAY of doing it ( store 1 in the table for n[5][coin(5,10)]) for this case



that's why n[i][m] = n[i-1][m]



can you explain the first if case? n[i][m] = n[i-1][m] + n[i][m - coins[i]]?
Full Post