Returns minimum count to reach target given necessary unlimited coins of that denomation.

min_count_dp.py

import functools as ft

# See: https://github.com/python/cpython/blob/e2d65630f36712dbdbf7711520c985c526a5cc25/Lib/functools.py#L525
@ft.lru_cache
def min_count(L: list, target: int, sum_count = None) -> int:
    """Returns minimum count to reach target given necessary unlimited coins of that denomation."""
    if not L: return -1
    sum_count = sum_count or 0
    if target < 0:
        return float('inf')
    if target == 0:
        return sum_count
    return min([min_count(L, target-num, sum_count + 1) for num in L if num <= target] or [0]) or -1
        
        
assert min_count([20,10,5],13) == -1
assert min_count([20,10,5],30) == 2
assert min_count([4,3,1],6) == 2