Programmazione dinamica
La programmazione dinamica è “l’arte” di costruire uno stato basandosi su stati precedentemente calcolati. Quando eseguiamo dei calcoli, spesso facciamo affidamento sui valori già determinati in precedenza. Un esempio classico sono i numeri di Fibonacci, che possono essere calcolati tramite programmazione dinamica:
Per calcolare
fib(2) utilizziamo i valori fib(1) e fib(0), ottenendo fib(2) = 1. Per trovare il valore successivo nella sequenza di Fibonacci, riutilizziamo il valore appena calcolato – fib(3) = fib(2) + fib(1) = 1 + 1 = 2. Allo stesso modo, fib(4) = fib(3) + fib(2) = 2 + 1 = 3 e fib(5) = fib(4) + fib(3) = 3 + 2 = 5, e così via.A ogni iterazione, calcoliamo il valore attuale della sequenza di Fibonacci utilizzando i risultati delle iterazioni precedenti. Possiamo implementarlo con una lista:
n = ...
fib = [0, 1] # fib[0] = 0, fib[1] = 1
for i in range(2, n + 1):
fib.append(fib[i - 1] + fib[i - 2])
print(fib[n])Se
n = 5, il programma stamperà 5; se n = 7, stamperà 13.Questo processo di calcolo ripetuto dello stato corrente (nel nostro caso, il numero di Fibonacci) sulla base degli stati precedenti è l’essenza della programmazione dinamica.
💡
La programmazione dinamica è una tecnica per costruire lo stato corrente in base agli stati precedenti.
Sfida - Numeri di Tribonacci
Dopo aver giocato con i numeri di Fibonacci, hai deciso di passare ai numeri di Tribonacci. I numeri di Tribonacci sono definiti come segue:
Il tuo compito è trovare l’
n-esimo numero di Tribonacci.Input
L’input contiene un singolo intero
n (1 ≤ n ≤ 30).Output
L’output deve contenere l’
n-esimo numero di Tribonacci.Esempi
Input | Output |
2 | 1 |
4 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB