0Pricing
Coding Interview Prep · Lezione

Coin change e scala a costo minimo

Formuli le ricorrenze di coin-change e min-cost-climbing-stairs, scelga la direzione DP corretta e tracci manualmente i passaggi nella tabella

Coin change e scala a costo minimo è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.

Il problema del resto

Problema del resto (LeetCode #322): vengono forniti i tagli delle monete e un importo obiettivo. Occorre trovare il numero minimo di monete necessario per ottenere esattamente tale importo. È possibile usare un numero illimitato di monete di ciascun taglio. Si tratta di una classica variante dello zaino illimitato: ogni elemento, cioè ogni moneta, può essere usato un numero qualsiasi di volte. È uno dei problemi di DP più importanti, perché mette alla prova la capacità di formulare una ricorrenza da zero.

# Problem examples:
# coins=[1,5,6,9], amount=11 -> 2 (5+6 or 2+9? no: 5+6=11 YES)
# coins=[2],       amount=3  -> -1 (impossible)
# coins=[1,2,5],   amount=11 -> 3 (5+5+1)
# coins=[186,419,83,408], amount=6249 -> 20

# Key choices:
# - Try each coin denomination at each step
# - Minimum coins = 1 + minimum(coins to make amount - coin)
# - If amount < 0: impossible
# - If amount = 0: done (0 coins)

print('Coin change: unbounded knapsack, find minimum count')

Derivazione della ricorrenza del problema del resto

Si definisca dp[i] come il numero minimo di monete necessario per ottenere l'importo i. Per ogni importo i, si provi a usare ogni moneta c: se i >= c, allora dp[i] = min(dp[i], 1 + dp[i-c]). L'1 rappresenta la moneta appena utilizzata; dp[i-c] è la soluzione ottimale per l'importo rimanente. Questo presuppone una disponibilità illimitata di monete. Caso base: dp[0] = 0. Si inizializzino tutte le altre celle a infinito, per rappresentare gli importi non ancora ottenibili.

def coin_change(coins, amount):
    # dp[i] = min coins to make amount i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # base: 0 coins for amount 0

    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin and dp[i - coin] != float('inf'):
                dp[i] = min(dp[i], 1 + dp[i - coin])

    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 5, 6, 9], 11))  # 2
print(coin_change([2], 3))             # -1
print(coin_change([1, 2, 5], 11))      # 3

# Trace dp for coins=[1,5] amount=6:
# dp[0]=0, dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=4, dp[5]=1, dp[6]=2

Perché l'approccio greedy fallisce

L'approccio greedy, che sceglie sempre la moneta di taglio maggiore compatibile, fallisce nel problema del resto. Esempio: coins=[1, 3, 4], amount=6. L'approccio greedy sceglie 4 e poi 1+1, usando 3 monete. La soluzione ottimale è 3+3, con 2 monete. L'approccio greedy funziona con i tagli standard (1, 5, 10, 25 centesimi) perché, casualmente, soddisfano la proprietà greedy. Con insiemi di monete arbitrari, invece, è necessaria la DP. Questo è un punto classico nei colloqui: affermare che l'approccio greedy fallisce e spiegare il motivo dimostra solide capacità analitiche.

# Greedy failure example:
# coins=[1,3,4], amount=6
# Greedy: 4 (rem=2), 1 (rem=1), 1 (rem=0) -> 3 coins
# Optimal: 3 (rem=3), 3 (rem=0) -> 2 coins

def coin_change_greedy_wrong(coins, amount):
    coins_sorted = sorted(coins, reverse=True)
    count = 0
    for coin in coins_sorted:
        while amount >= coin:
            amount -= coin
            count += 1
    return count if amount == 0 else -1

print('Greedy:', coin_change_greedy_wrong([1,3,4], 6))  # 3 (WRONG)
print('DP:    ', coin_change([1,3,4], 6))               # 2 (CORRECT)

Problema del resto II: contare i modi

Problema del resto II (LeetCode #518) chiede di calcolare il numero di modi per ottenere l'importo, non il numero minimo di monete. La ricorrenza cambia: al posto di min si usa una somma. dp[i] += dp[i-coin] per ogni moneta. L'ordine di riempimento è importante: per contare ogni combinazione una sola volta, si inseriscono le monete nel ciclo esterno e gli importi nel ciclo interno. Invertendo i cicli si contano le permutazioni invece delle combinazioni, risolvendo un problema diverso.

def coin_change_ii(coins, amount):
    # dp[i] = number of ways to make amount i
    dp = [0] * (amount + 1)
    dp[0] = 1  # one way to make amount 0: use no coins

    # Outer loop: coins -- ensures each coin type processed once
    for coin in coins:
        # Inner loop: amounts
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]

print(coin_change_ii([1, 2, 5], 5))   # 4: [1,1,1,1,1],[1,1,1,2],[1,2,2],[5]
print(coin_change_ii([2], 3))          # 0: impossible
print(coin_change_ii([10], 10))        # 1

# Key: coin outer, amount inner = COMBINATIONS (unordered)
# Reverse (amount outer, coin inner) = PERMUTATIONS (ordered)

Scala a costo minimo: il problema

Salita delle scale a costo minimo (LeetCode #746) presenta una scala in cui ogni gradino ha un costo. È possibile salire di 1 o 2 gradini alla volta. Occorre trovare il costo minimo per raggiungere la cima, cioè un gradino oltre l'ultimo. È possibile iniziare gratuitamente dal gradino 0 o dal gradino 1. Questo problema combina elegantemente la ricorrenza della salita delle scale con il modello di minimizzazione dei costi del problema del resto, creando un naturale collegamento tra i due.

# cost = [10, 15, 20]
# Pay cost[i] to leave step i
# You can step to i+1 or i+2
# Goal: reach top (index 3) with minimum cost

# Path options:
# Start at 0: cost 10, go to 2: cost 20, done -> 30
# Start at 1: cost 15, go to 3: done -> 15  <- OPTIMAL
# Start at 0: cost 10, go to 1: cost 15 -> 25

cost = [10, 15, 20]
# Optimal: start at step 1, pay 15, jump to top -> cost = 15
print('Expected:', 15)

Scala a costo minimo: ricorrenza

Si definisca dp[i] come il costo minimo per raggiungere il gradino i. Si arriva al gradino i pagando cost[i-1] dal gradino i-1 oppure cost[i-2] dal gradino i-2. Pertanto dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). Casi base: dp[0] = 0, perché si parte prima della scala gratuitamente; dp[1] = 0, perché è possibile iniziare gratuitamente anche dal gradino 1. La risposta è dp[n], dove n = len(cost).

def min_cost_climbing_stairs(cost):
    n = len(cost)
    # dp[i] = minimum cost to reach step i
    # Steps 0 to n; step n is the top (goal)
    dp = [0] * (n + 1)
    # dp[0] = 0 (free to start here)
    # dp[1] = 0 (free to start here)
    for i in range(2, n + 1):
        dp[i] = min(dp[i-1] + cost[i-1],   # step from i-1
                    dp[i-2] + cost[i-2])    # jump from i-2
    return dp[n]

print(min_cost_climbing_stairs([10, 15, 20]))      # 15
print(min_cost_climbing_stairs([1,100,1,1,1,100,1,1,100,1]))  # 6

Scala a costo minimo: ottimizzazione dello spazio

Poiché dp[i] dipende solo da dp[i-1] e dp[i-2], è possibile ridurre lo spazio a O(1) usando due variabili, proprio come per Fibonacci. Si sostituisce l'array con prev2 e prev1, aggiornandole a ogni passaggio. Questa è un'ottimizzazione standard, esprimibile in una sola riga, che gli intervistatori si aspettano dopo aver presentato la soluzione con tabella O(n). È sempre opportuno menzionarla spontaneamente: «Possiamo ridurre lo spazio a O(1), perché ci servono solo gli ultimi due valori».

def min_cost_optimised(cost):
    n = len(cost)
    prev2, prev1 = 0, 0  # dp[0] and dp[1]
    for i in range(2, n + 1):
        curr = min(prev1 + cost[i-1], prev2 + cost[i-2])
        prev2, prev1 = prev1, curr
    return prev1

print(min_cost_optimised([10, 15, 20]))  # 15
print(min_cost_optimised([1,100,1,1,1,100,1,1,100,1]))  # 6

# Alternative: directly use cost array as rolling storage
def min_cost_v2(cost):
    n = len(cost)
    for i in range(2, n):
        cost[i] += min(cost[i-1], cost[i-2])
    return min(cost[-1], cost[-2])

from copy import deepcopy
cost_test = [10,15,20]
print(min_cost_v2(deepcopy(cost_test)))  # 15

Formulazione DP alternativa

Alcuni problemi ammettono diverse formulazioni DP valide. Per la scala a costo minimo, si può definire dp[i] come il costo minimo per LASCIARE il gradino i, pagando cost[i] e scegliendo di andare a i+1 o i+2. In tal caso dp[i] = cost[i] + min(dp[i+1], dp[i+2]), riempiendo la tabella da destra verso sinistra; la risposta è min(dp[0], dp[1]). Entrambe le formulazioni sono corrette. Si eserciti a spiegare quale formulazione ha scelto e perché: dimostra padronanza della DP.

def min_cost_alternative(cost):
    n = len(cost)
    # dp[i] = min cost when starting FROM step i
    # Fill right to left
    dp = cost[:] + [0]  # dp[n] = 0 (already at top)
    for i in range(n - 1, -1, -1):
        # Pay cost[i], then choose i+1 or i+2
        if i + 2 <= n:
            dp[i] = cost[i] + min(dp[i+1], dp[i+2])
        else:
            dp[i] = cost[i] + dp[i+1]
    # Can start at step 0 or step 1
    return min(dp[0], dp[1])

print(min_cost_alternative([10, 15, 20]))  # 15
print(min_cost_alternative([1,100,1,1,1,100,1,1,100,1]))  # 6

Collegare problema del resto e scala

Il problema del resto e la scala a costo minimo sono entrambi esempi dello stesso modello DP: a ogni passo si sceglie un'opzione da un insieme finito e si ottimizza un obiettivo lungo la sequenza delle scelte. Le differenze sono solo di forma: il problema del resto tiene traccia del numero di monete, aggiungendo 1 per ogni moneta, mentre la scala tiene traccia del costo, aggiungendo cost[i] per ogni gradino. Riconoscere questa struttura comune consente di risolvere nuovi problemi di DP riconducendoli a modelli già noti.

# Shared pattern:
# dp[state] = optimise(dp[prev_state_1] + cost_1,
#                      dp[prev_state_2] + cost_2, ...)

# Coin change:  dp[amount] = min(1 + dp[amount - coin] for coin in coins)
# Min stair:    dp[step]   = min(cost[step-1]+dp[step-1], cost[step-2]+dp[step-2])
# Max path sum: dp[cell]   = max(dp[top], dp[left]) + grid[cell]
# House robber: dp[house]  = max(dp[house-1], dp[house-2] + value[house])

# All four are the SAME pattern with different:
# - State representation
# - Number of choices per state
# - Objective (min/max)
# - Transition cost
print('DP pattern: state + choices + objective + cost = template')

Numero minimo di quadrati perfetti

Quadrati perfetti (LeetCode #279) chiede il numero minimo di quadrati perfetti (1, 4, 9, 16, ...) la cui somma sia n. È esattamente un problema del resto in cui le «monete» sono i numeri quadrati perfetti. Si generino tutti i quadrati perfetti fino a n, quindi si applichi il problema del resto. La DP richiede O(n * sqrt(n)) tempo. Il teorema dei quattro quadrati di Lagrange stabilisce che la risposta è al massimo 4, consentendo anche un approccio matematico in O(sqrt(n)); tuttavia, la soluzione attesa è quella con DP.

import math

def num_squares(n):
    # Generate all perfect squares up to n
    squares = [i*i for i in range(1, int(math.sqrt(n)) + 1)]
    # Coin change with squares as 'coins'
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        for sq in squares:
            if i >= sq:
                dp[i] = min(dp[i], 1 + dp[i - sq])
    return dp[n]

print(num_squares(12))  # 3: 4+4+4
print(num_squares(13))  # 2: 4+9
print(num_squares(1))   # 1: 1

Debug della DP: errori comuni

Errori comuni nella DP: caso base errato (dp[0] impostato in modo scorretto), ordine di riempimento errato (si accede a un valore non ancora calcolato), errore di un'unità nella definizione dello stato (dp[i] rappresenta il costo PER raggiungere i oppure il costo per lasciare i) e mancata restituzione di -1 quando rimane infinito (casi impossibili). Si eseguano sempre i test sui casi più semplici, come input vuoto, un solo elemento e target=0, prima di provare input più grandi.

# Common DP debugging checklist:
# 1. Base case: what is dp[0]? dp[1]? Are they correct?
# 2. State definition: write it in English before coding
# 3. Recurrence: trace manually on a 3-element example
# 4. Fill order: dependency arrows point left/up? Fill left/up first
# 5. Infinity check: return -1 or 0 when dp[target] == inf?
# 6. Array bounds: dp has size n+1 for 0..n, or n for 0..n-1?

# Quick test template:
def test_coin_change():
    assert coin_change([1], 0) == 0     # base case
    assert coin_change([1], 1) == 1     # single coin
    assert coin_change([2], 3) == -1    # impossible
    assert coin_change([1,5,6,9], 11) == 2
    print('All tests passed!')

test_coin_change()

Controllo rapido

Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.

Riepilogo della lezione

In questa lezione ha imparato: la DP del problema del resto per il numero minimo di monete (zaino illimitato) e il motivo per cui l'approccio greedy fallisce, il problema del resto II per contare le combinazioni usando le monete nel ciclo esterno e gli importi in quello interno, oltre alla scala a costo minimo con le formulazioni da sinistra a destra e da destra a sinistra. Ora esploreremo i modelli di DP 1D con il ladro di case, l'algoritmo di Kadane e la suddivisione delle parole.

Domande Frequenti

La lezione «Coin change e scala a costo minimo» è gratuita?

Sì — il testo completo di «Coin change e scala a costo minimo» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.

Cosa imparerò in «Coin change e scala a costo minimo»?

Formuli le ricorrenze di coin-change e min-cost-climbing-stairs, scelga la direzione DP corretta e tracci manualmente i passaggi nella tabella Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare Coding Interview Prep?

Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.

Quanto tempo richiede la lezione «Coin change e scala a costo minimo»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?

Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

  1. Riconoscere la DP: sottoproblemi sovrapposti
  2. DP top-down con memoisation
  3. DP bottom-up con tabulation
  4. Coin change e scala a costo minimo
← Torna a Coding Interview Prep