Memoized to DP solution - Making Change

Vote count:

0

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.

asked 2 mins ago

uki

3,110