## samedi 28 juin 2014

### Memoized to DP solution - Making Change

Recently I read a problem to practice DP. I wasn't able to come up with one, so I tried a recursive solution which I later modified to use memoization. The problem statement is as follows :-

Making Change. You are given n types of coin denominations of values v(1) < v(2) < ... < v(n) (all integers). Assume v(1) = 1, so you can always make change for any amount of money C. Give an algorithm which makes change for an amount of money C with as few coins as possible. [on problem set 4]

I got the question from here

My solution was as follows :-

``def memoized_make_change(L, index, cost, d):    if index == 0:        return cost    if (index, cost) in d:        return d[(index, cost)]    count = cost / L[index]    val1 = memoized_make_change(L, index-1, cost%L[index], d) + count    val2 = memoized_make_change(L, index-1, cost, d)    x = min(val1, val2)    d[(index, cost)] = x    return x``

This is how I've understood my solution to the problem. Assume that the denominations are stored in L in ascending order. As I iterate from the end to the beginning, I have a choice to either choose a denomination or not choose it. If I choose it, I then recurse to satisfy the remaining amount with lower denominations. If I do not choose it, I recurse to satisfy the current amount with lower denominations.

Either way, at a given function call, I find the best(lowest count) to satisfy a given amount.

Could I have some help in bridging the thought process from here onward to reach a DP solution? I'm not doing this as any HW, this is just for fun and practice. I don't really need any code either, just some help in explaining the thought process would be perfect.