Dynamic Programming

In [28]:

    

def recursive(coins, change):
    if change in coins:
        return 1
    else:
        return min([
            1 + recursive(coins, change - coin)
            for coin in coins
        ])


    

In [36]:

    

recursive([1, 2], 5)


    

    
Out[36]:





3

In [51]:

    

test_cases = [
    (([1, 2, 3], 3), 1),
    (([1, 2, 3], 2), 1),
    (([1, 2, 3], 5), 2),
    (([1, 2, 3], 10), 4),
    (([25, 21, 10, 5, 1], 63), 3),  # max depth exceeded
    (([25, 10, 5, 1], 63), 6)  # max depth exceeded
]


    

In [199]:

    

def run_test_cases(f, n=None):
    if n is None:
        n = len(test_cases)
    return all([f(*input_) == expected for input_, expected in test_cases[:n]])


    

In [200]:

    

assert run_test_cases(recursive, 4)


    

In [201]:

    

def recursive_memory(coins, change):
    results = {}
    
    def recurse(change):
        if change in results:
            return results[change]
        else:
            if change in coins:
                results[change] = 1
                return 1
            else:
                min_ = change
                for coin in [c for c in coins if c <= change]:
                    diff = change - coin
                    n = 1 + (results[diff] if diff in results else recurse(diff))
                    min_ = min(min_, n)

                results[change] = min_
                return min_
    
    return recurse(change)


    

In [204]:

    

assert run_test_cases(recursive_memory)


    

In [228]:

    

def dynamic_programming(coins, n):
    results = [0] * (n + 1)
    for i in range(1, n + 1):
        min_ = i
        for c in coins:
            if c <= i:
                tmp = 1 + results[i - c]
                min_ = min(min_, tmp)
                
        results[i] = min_
            
    return results[-1]


    

In [229]:

    

assert run_test_cases(dp)