Pattern: Dynamic Programming

Il pattern Dynamic Programming (programmazione dinamica) permette di risolvere problemi complessi dividendoli in sottoproblemi più semplici i cui risultati vengono riutilizzati. È particolarmente utile quando i sottoproblemi si ripetono più volte.

🚀 Quando usarlo

Usa la programmazione dinamica quando:

• Il problema può essere suddiviso in sottoproblemi che si sovrappongono
• Esiste una struttura ricorsiva o un'ottimizzazione di tipo "scelta ottimale"
• Vuoi ridurre la complessità da esponenziale a polinomiale memorizzando risultati già calcolati

🧰 Tecniche principali

Tecnica	Descrizione
Top-Down	Uso della memorizzazione (memoization) con ricorsione
Bottom-Up	Costruzione iterativa di una tabella di soluzioni

✏️ Esempio classico: Serie di Fibonacci

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

✅ Complessità:

• Tempo: O(n)
• Spazio: O(n)

🧩 Problemi comuni

Nome	Difficoltà	Pattern	Link
Fibonacci Numbers	Easy	Top-Down	Leetcode #509
Coin Change	Medium	Bottom-Up	Leetcode #322
Edit Distance	Hard	Bottom-Up	Leetcode #72
Longest Increasing Subsequence	Medium	Bottom-Up	Leetcode #300

💡 Consigli utili

• Disegna la tabella o l'albero delle chiamate per visualizzare i sottoproblemi
• Verifica se è possibile ottimizzare lo spazio mantenendo solo le righe o colonne necessarie
• Usa la memoization solo se i sottoproblemi sono davvero ripetitivi, altrimenti potrebbe non convenire

📚 Continua con

👉 Divide and Conquer →