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

Some interview question can be soled by dynamic programming. One of such is coin problem - express an amount of money with minimal coin number.

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

For 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 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 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 got:

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


all / emacs / java / python


admin(1), anki(1), blog(1), css(2), cygwin(2), emacs(3), fs(1), git(1), hg(2), html(1), interview(11), java(1), js(3), lighttpd(1), mobile(1), naming(1), printer(1), problem(5), quiz(6), rst(1), security(1), sql(1), srs(1), unit(1), utils(1), vcs(1), web(2), win(2)