interview-questions/arrays-and-strings/add_coins.py

# Given a list of nums and a target s, find the minimum number of numbers from
# the list that add up to s

import pytest

def test_add_coins():
    list = [1, 3, 5]
    s = 11
    assert add_coins(list,s) == 3

def add_coins(list, s):
    if s < min(list) or s <= 0: return 0
    dp = [float('inf')] * (s+1)
    dp[0] = 0
    for i_s in range(s+1):
        for i_v in range(len(list)):
            if list[i_v] <= i_s and dp[i_s - list[i_v]] + 1 < dp[i_s]:
                dp[i_s] = dp[i_s - list[i_v]] + 1
    return dp[-1]