Oleksandr Gavenko's blog
2017-01-19 01:45 Solution for coin problem by dynamic programming

Some interview question can be solved by dynamic programming.

One of such is a coin problem - express an amount of money with the minimal coin number.

Dynamic programming is all about solving task by compounding solutions of smaller sub-tasks. Most famous example is a definition of Fibonacci number f(n) = f(n-1) + f(n-2).

For the coin task recursive solution is:

def score(solution):
    return sum(solution.values())

def solve(amount, coins):
    if amount in coins:
        return {amount: 1}
    best_solution = None
    best_score = None
    for coin in coins:
        if amount < coin:
        solution = solve(amount - coin, coins)
        if not solution:
        curr_score = score(solution)+1
        if not best_score or curr_score < best_score:
            if coin in solution:
                solution[coin] += 1
                solution[coin] = 1
            best_solution = solution
            best_score = curr_score
    return best_solution

Memoization should be used to reduce the size of recursion tree.

Alternatively instead of recursion we may start from the smallest sub-problems and iteratively build solution for larger and larger problems until we reached a desired solution.

Unfortunately we may calculate unnecessary sub-problems with iterative approach, this is not happened with recursion and memoization approach.


print solve(10, set([1, 2, 3]))
print solve(10, set([2, 3]))
print solve(11, set([2, 5]))
print solve(32, set([7, 10]))

I've got:

{1: 1, 3: 3}
{2: 2, 3: 2}
{2: 3, 5: 1}
interview, problem


all / emacs / java


adb(1), admin(1), android(1), anki(1), ansible(2), aop(1), blog(2), bytecode(1), c(1), css(2), cygwin(2), driver(1), emacs(3), fs(1), git(3), google(1), gradle(1), hardware(1), hg(2), html(1), interview(13), java(4), js(3), lang(2), lighttpd(1), markdown(1), mobile(1), naming(1), oracle(1), print(1), problem(5), python(1), quiz(6), rst(2), security(3), spring(2), sql(2), srs(1), style(1), tls(2), txt(1), unit(1), utils(1), vcs(3), web(2), win(2), windows(1)