Programação Dinâmica
Programação dinâmica é a “arte” de construir um determinado estado com base nos estados anteriores. Quando fazemos cálculos, costumamos aproveitar os valores que já foram calculados durante a execução. Os números de Fibonacci são um ótimo exemplo, pois podem ser calculados utilizando programação dinâmica:
Para calcular
fib(2), usamos os valores fib(1) e fib(0). Dessa forma, obtemos fib(2) = 1. Para conseguir o valor seguinte da sequência de Fibonacci, fazemos uso do valor que calculámos anteriormente — fib(3) = fib(2) + fib(1) = 1 + 1 = 2. Do mesmo modo, fib(4) = fib(3) + fib(2) = 2 + 1 = 3 e fib(5) = fib(4) + fib(3) = 3 + 2 = 5, e assim a sequência prossegue.Em cada iteração, calculamos o valor atual da sequência de Fibonacci com base nos estados anteriores que já tínhamos computado. Podemos implementar essa ideia utilizando uma 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])Para
n = 5, o programa mostraria 5, enquanto para n = 7 mostraria 13.O processo de calcular repetidamente o estado atual (neste caso, o número de Fibonacci correspondente) com base nos estados anteriores é a essência da Programação Dinâmica.
💡
Programação dinâmica é uma técnica que permite construir o estado atual com base nos estados anteriores.
Desafio - Números de Tribonacci
Depois de brincares com os números de Fibonacci, decidiste experimentar os números de Tribonacci para variar. Os números de Tribonacci são definidos como:
A tua tarefa é encontrar o
n-ésimo número de Tribonacci.Entrada
A entrada contém um único inteiro
n (1 ≤ n ≤ 30).Saída
A saída deve conter o
n-ésimo número de Tribonacci.Exemplos
Entrada | Saída |
2 | 1 |
4 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB