Détecter l'échec du glouton

On construit un tableau dp où dp[k] est le nombre minimal de pièces pour rendre $k$.

def minimum_pieces(systeme, somme):
    INF = float("inf")
    dp = [0] + [INF] * somme
    for k in range(1, somme + 1):
        for v in systeme:
            if v <= k and dp[k - v] + 1 < dp[k]:
                dp[k] = dp[k - v] + 1
    return dp[somme]

print(minimum_pieces([1, 3, 4], 6))   # 2  (3 + 3)
# Le glouton donnerait 3 pieces (4 + 1 + 1)