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