Programación Dinámica
La programación dinámica es el “arte” de construir un determinado estado basándose en los estados anteriores. Al realizar cálculos, a menudo utilizamos los valores previos que se generaron durante la ejecución. Los números de Fibonacci son un excelente ejemplo que puede calcularse empleando programación dinámica:
Para calcular
fib(2), usaríamos los valores fib(1) y fib(0). De este modo, obtenemos fib(2) = 1. Para obtener el siguiente valor en la secuencia de Fibonacci, reutilizamos el valor calculado anteriormente: fib(3) = fib(2) + fib(1) = 1 + 1 = 2. De manera similar, fib(4) = fib(3) + fib(2) = 2 + 1 = 3 y fib(5) = fib(4) + fib(3) = 3 + 2 = 5, y la secuencia continúa.En cada iteración, calculamos el valor actual de la secuencia de Fibonacci utilizando los estados previos calculados con anterioridad. Esto puede implementarse con una lista:
n = ...
fib = [0, 1] # fib[0] es 0, fib[1] es 1
for i in range(2, n + 1):
fib.append(fib[i - 1] + fib[i - 2])
print(fib[n])Para un valor
n = 5, el programa imprimiría 5, mientras que para un valor n = 7 imprimiría 13.El proceso de calcular repetidamente el estado actual (en nuestro caso, el número de Fibonacci actual) usando los estados anteriores es la esencia de la Programación Dinámica.
💡
La programación dinámica es una técnica para construir el estado actual basándose en los estados previos.
Desafío - Números de Tribonacci
Después de divertirte con los números de Fibonacci, te aburriste y decidiste probar con los números de Tribonacci (Tribonacci numbers). Estos números se definen así:
Tu tarea es encontrar el
n-ésimo número de Tribonacci.Entrada
La entrada contiene un único entero
n (1 ≤ n ≤ 30).Salida
La salida debe contener el
n-ésimo número de Tribonacci.Ejemplos
Entrada | Salida |
2 | 1 |
4 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB