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:
            continue
        solution = solve(amount - coin, coins)
        if not solution:
            continue
        curr_score = score(solution)+1
        if not best_score or curr_score < best_score:
            if coin in solution:
                solution[coin] += 1
            else:
                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.

For:

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}
None
interview, problem

Feeds

all / emacs / java / python

Tags

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

Archive