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:
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 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.

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've got:

```{1: 1, 3: 3}
{2: 2, 3: 2}
{2: 3, 5: 1}
None```
interview, problem ## Feeds

all / emacs / java

## Tags

adb(1), admin(1), android(1), anki(1), ansible(2), blog(2), 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(3), 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(1), sql(2), srs(1), style(1), tls(2), txt(1), unit(1), utils(1), vcs(3), web(2), win(2), windows(1)