2. problema de Fibonacci consiste em calcular o n-ésimo número da sequência de Fibonacci, onde a sequência é definida como: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) para ngeqslant 2 Implemente um algoritmo que leia um inteiro N(Nlt 46) e mostre os N primeiros números dessa série usando programação dinâmica . Na programação dinâmica é necessário usar uma tabela (vetor) para armazenar os resultados intermediários , evitando cálculos repetidos . Recomendo utilizar o beecrowd (https://judge beecrowd.com/pt/problems /view/1151) para testar a implementação , lembrando que a solução DEVE envolver o uso de Programação Dinâmica.

Para resolver esse problema usando programação dinâmica, podemos utilizar uma tabela (vetor) para armazenar os resultados intermediários. Vamos implementar um algoritmo em Python que leia um inteiro N (N < 46) e mostre os N primeiros números da sequência de Fibonacci usando programação dinâmica.<br /><br />```python<br />def fibonacci(N):<br /> if N <= 0:<br /> return []<br /> elif N == 1:<br /> return [0]<br /> elif N == 2:<br /> return [0, 1]<br /><br /> # Inicialização da tabela (vetor) para armazenar os resultados intermediários<br /> tabela = [0] * (N + 1)<br /> tabela[1] = 1<br /><br /> # Preenchimento da tabela com os números da sequência de Fibonacci<br /> for i in range(2, N + 1):<br /> tabela[i] = tabela[i - 1] + tabela[i - 2]<br /><br /> return tabela[2:N+1]<br /><br /># Leitura do valor de N pelo usuário<br />N = int(input("Digite um inteiro N (N < 46): "))<br /><br /># Cálculo e exibição dos N primeiros números da sequência de Fibonacci<br />sequencia = fibonacci(N)<br />print(sequencia)<br />```<br /><br />Explicação do código:<br />1. A função `fibonacci` recebe um inteiro N como entrada e retorna uma lista com os N primeiros números da sequência de Fibonacci.<br />2. Se N for menor ou igual a 0, a função retorna uma lista vazia.<br />3. Se N for igual a 1, a função retorna uma lista com o número 0.<br />4. Se N for igual a 2, a função retorna uma lista com os números 0 e 1.<br />5. Caso contrário, inicializamos uma tabela (vetor) com tamanho N+1 para armazenar os resultados intermediários.<br />6. Preenchimos a tabela com os números da sequência de Fibonacci, utilizando a fórmula de recorrência dada no enunciado.<br />7. Retornamos a parte da tabela que contém os N primeiros números da sequência de Fibonacci (excluindo o índice 0 e 1).<br /><br />Ao executar o programa, o usuário será solicitado a digitar um inteiro N (menor que 46). Em seguida, o programa calculará e exibirá os N primeiros números da sequência de Fibonacci utilizando programação dinâmica.