--- title: "Fibonacci com Programação Dinâmica" url: "https://rustlang.com.br/algoritmos/fibonacci-dp/" markdown_url: "https://rustlang.com.br/algoritmos/fibonacci-dp.MD" description: "Aprenda programação dinâmica em Rust com Fibonacci: recursão ingênua, memoização, tabulação e otimização de espaço com análise Big-O completa." date: "2026-02-24" author: "Equipe Rust Brasil" --- # Fibonacci com Programação Dinâmica Aprenda programação dinâmica em Rust com Fibonacci: recursão ingênua, memoização, tabulação e otimização de espaço com análise Big-O completa. A sequência de Fibonacci é o ponto de partida clássico para aprender **programação dinâmica** (DP). Embora o problema em si seja simples --- cada número é a soma dos dois anteriores --- ele ilustra perfeitamente os dois pilares de DP: **subestrutura ótima** e **subproblemas sobrepostos**. Nesta página, partiremos de uma solução recursiva ingênua com complexidade exponencial e chegaremos a soluções lineares e até com espaço constante, tudo em Rust puro. Na prática, variações da recorrência de Fibonacci aparecem em contagem de caminhos em grades, análise de algoritmos de divisão e conquista, modelagem financeira e até na natureza (filotaxia, proporção áurea). Dominar as técnicas aqui apresentadas prepara você para problemas muito mais complexos de DP. ## O Problema Dado um inteiro não negativo `n`, calcule o n-ésimo número de Fibonacci, definido por: ``` F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) para n >= 2 ``` **Exemplo de entrada/saída:** | Entrada (n) | Saída F(n) | |-------------|-----------| | 0 | 0 | | 1 | 1 | | 5 | 5 | | 10 | 55 | | 50 | 12586269025 | ## Abordagem Ingênua (Força Bruta) A tradução direta da definição matemática gera uma função recursiva pura: ```rust /// Calcula F(n) de forma recursiva ingênua. /// ATENÇÃO: complexidade exponencial O(2^n) — impraticável para n > ~40. fn fib_ingenua(n: u64) -> u64 { if n <= 1 { return n; } fib_ingenua(n - 1) + fib_ingenua(n - 2) } fn main() { // Funciona para valores pequenos for i in 0..=10 { println!("F({}) = {}", i, fib_ingenua(i)); } // fib_ingenua(50) levaria MINUTOS ou mais! } ``` ### Árvore de chamadas para F(5) O diagrama abaixo mostra por que essa abordagem é lenta --- os mesmos subproblemas são recalculados muitas vezes: ``` F(5) / \ F(4) F(3) / \ / \ F(3) F(2) F(2) F(1) / \ / \ / \ F(2) F(1) F(1) F(0) F(1) F(0) / \ F(1) F(0) ``` Observe que `F(3)` é calculado **2 vezes**, `F(2)` é calculado **3 vezes** e `F(1)` é calculado **5 vezes**. Para valores grandes de `n`, essa redundância cresce exponencialmente. ## Identificando Subestrutura Ótima A programação dinâmica se aplica quando duas condições são satisfeitas: 1. **Subestrutura ótima**: a solução ótima do problema pode ser construída a partir de soluções ótimas de subproblemas. No caso de Fibonacci, `F(n)` depende diretamente de `F(n-1)` e `F(n-2)`. 2. **Subproblemas sobrepostos**: os mesmos subproblemas aparecem repetidamente. Como vimos na árvore acima, `F(3)`, `F(2)`, etc., são recalculados várias vezes. A ideia central é: **calcule cada subproblema apenas uma vez e armazene o resultado**. Isso pode ser feito de duas formas: - **Top-Down (Memoização)**: mantenha a recursão, mas guarde os resultados já calculados em um cache (HashMap ou Vec). - **Bottom-Up (Tabulação)**: preencha uma tabela iterativamente, dos casos base até o resultado desejado. ## Visualização da Tabela DP Para `n = 7`, a tabela bottom-up é preenchida da esquerda para a direita: ``` Índice: 0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+---+ Valor: | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13| +---+---+---+---+---+---+---+---+ ^ ^ | | | dp[2] = dp[1] + dp[0] = 1 + 0 = 1 | caso base caso base Passo a passo: dp[0] = 0 (caso base) dp[1] = 1 (caso base) dp[2] = dp[1] + dp[0] = 1 + 0 = 1 dp[3] = dp[2] + dp[1] = 1 + 1 = 2 dp[4] = dp[3] + dp[2] = 2 + 1 = 3 dp[5] = dp[4] + dp[3] = 3 + 2 = 5 dp[6] = dp[5] + dp[4] = 5 + 3 = 8 dp[7] = dp[6] + dp[5] = 8 + 5 = 13 ``` ## Complexidade | Abordagem | Tempo | Espaço | Observação | |-----------|-------|--------|------------| | Força Bruta (recursão) | O(2^n) | O(n) pilha | Impraticável para n > 40 | | Top-Down (Memoização) | O(n) | O(n) cache + pilha | Risco de stack overflow para n grande | | Bottom-Up (Tabulação) | O(n) | O(n) vetor | Iterativo, sem risco de pilha | | Otimizado (duas variáveis) | O(n) | O(1) | Melhor abordagem geral | ## Implementação: Top-Down (Memoização) Usamos um `HashMap` para armazenar resultados já calculados. Cada subproblema é resolvido no máximo uma vez. ```rust use std::collections::HashMap; /// Calcula F(n) usando memoização com HashMap. /// Cada subproblema é calculado apenas uma vez: O(n) tempo, O(n) espaço. fn fib_memo(n: u64, cache: &mut HashMap) -> u64 { // Se já calculamos, retornamos do cache if let Some(&valor) = cache.get(&n) { return valor; } // Casos base let resultado = if n <= 1 { n } else { // Chamadas recursivas com memoização let a = fib_memo(n - 1, cache); let b = fib_memo(n - 2, cache); a + b }; // Armazena no cache antes de retornar cache.insert(n, resultado); resultado } fn main() { let mut cache = HashMap::new(); for i in 0..=10 { println!("F({}) = {}", i, fib_memo(i, &mut cache)); } // Agora funciona instantaneamente mesmo para valores grandes cache.clear(); println!("F(50) = {}", fib_memo(50, &mut cache)); // 12586269025 } ``` **Alternativa com `Vec`**: para Fibonacci, onde os índices são inteiros consecutivos a partir de 0, um `Vec` é mais eficiente que um `HashMap`: ```rust /// Memoização com Vec — acesso O(1) em vez de O(1) amortizado do HashMap. fn fib_memo_vec(n: usize, cache: &mut Vec>) -> u64 { if let Some(valor) = cache[n] { return valor; } let resultado = if n <= 1 { n as u64 } else { fib_memo_vec(n - 1, cache) + fib_memo_vec(n - 2, cache) }; cache[n] = Some(resultado); resultado } fn main() { let n = 50; let mut cache = vec![None; n + 1]; println!("F({}) = {}", n, fib_memo_vec(n, &mut cache)); } ``` ## Implementação: Bottom-Up (Tabulação) A abordagem iterativa elimina a recursão e preenche a tabela dos casos base até `n`: ```rust /// Calcula F(n) com tabulação bottom-up. /// O(n) tempo, O(n) espaço. fn fib_tabular(n: usize) -> u64 { if n <= 1 { return n as u64; } // Cria a tabela DP com n+1 posições let mut dp = vec![0u64; n + 1]; // Casos base dp[0] = 0; dp[1] = 1; // Preenche a tabela iterativamente for i in 2..=n { dp[i] = dp[i - 1] + dp[i - 2]; } dp[n] } fn main() { for i in 0..=10 { println!("F({}) = {}", i, fib_tabular(i)); } println!("F(50) = {}", fib_tabular(50)); // 12586269025 println!("F(90) = {}", fib_tabular(90)); // 2880067194370816120 } ``` ## Otimização de Espaço Observe que `F(n)` depende apenas de `F(n-1)` e `F(n-2)`. Não precisamos manter toda a tabela --- apenas os dois valores anteriores: ```rust /// Calcula F(n) usando apenas duas variáveis. /// O(n) tempo, O(1) espaço — a versão mais eficiente. fn fib_otimizado(n: u64) -> u64 { if n <= 1 { return n; } let mut anterior = 0u64; // F(i-2) let mut atual = 1u64; // F(i-1) for _ in 2..=n { let proximo = anterior + atual; anterior = atual; atual = proximo; } atual } fn main() { // Verificação de todos os métodos for i in 0..=20 { let resultado = fib_otimizado(i); println!("F({:2}) = {}", i, resultado); } println!("\nF(50) = {}", fib_otimizado(50)); println!("F(93) = {}", fib_otimizado(93)); // Máximo que cabe em u64 } ``` **Versão com iterador**: para quem quer explorar o sistema de iteradores de Rust: ```rust /// Iterador infinito de Fibonacci usando o sistema de iteradores de Rust. struct FibIterator { atual: u64, proximo: u64, } impl FibIterator { fn new() -> Self { FibIterator { atual: 0, proximo: 1 } } } impl Iterator for FibIterator { type Item = u64; fn next(&mut self) -> Option { let valor = self.atual; let novo_proximo = self.atual + self.proximo; self.atual = self.proximo; self.proximo = novo_proximo; Some(valor) } } fn main() { // Primeiros 15 números de Fibonacci let fibs: Vec = FibIterator::new().take(15).collect(); println!("Primeiros 15: {:?}", fibs); // O n-ésimo Fibonacci (0-indexado) let f50 = FibIterator::new().nth(50).unwrap(); println!("F(50) = {}", f50); // 12586269025 } ``` ## Reconstruindo a Solução No caso de Fibonacci, o "resultado" é o próprio valor numérico, então não há reconstrução de caminho. Porém, em problemas derivados (como contar caminhos em uma grade), a reconstrução segue o mesmo princípio: a partir do resultado final, percorremos a tabela DP de volta identificando quais subproblemas contribuíram. Para ilustrar, considere o problema de **decompor F(n) em soma de Fibonacci anteriores** (representação de Zeckendorf): ```rust /// Encontra a representação de Zeckendorf de um número: /// decomposição em números de Fibonacci não consecutivos. fn zeckendorf(mut n: u64) -> Vec { if n == 0 { return vec![0]; } // Gera todos os Fibonacci até n let mut fibs = vec![1u64, 2]; loop { let proximo = fibs[fibs.len() - 1] + fibs[fibs.len() - 2]; if proximo > n { break; } fibs.push(proximo); } // Algoritmo guloso: escolhe o maior Fibonacci possível let mut resultado = Vec::new(); for &f in fibs.iter().rev() { if f <= n { resultado.push(f); n -= f; } if n == 0 { break; } } resultado } fn main() { let n = 100; let decomposicao = zeckendorf(n); println!("{} = {:?} (soma: {})", n, decomposicao, decomposicao.iter().sum::()); // 100 = [89, 8, 3] (soma: 100) } ``` ## Exercícios Práticos 1. **Fibonacci com módulo**: Calcule `F(n) mod 10^9 + 7` para valores enormes de `n` (até 10^18) usando exponenciação de matrizes. Dica: use a identidade matricial `[[1,1],[1,0]]^n`. 2. **Tribonacci**: Adapte as soluções para a sequência de Tribonacci, onde `T(n) = T(n-1) + T(n-2) + T(n-3)`, com `T(0)=0, T(1)=0, T(2)=1`. 3. **Subir escadas**: Você pode subir uma escada de `n` degraus, subindo 1 ou 2 degraus por vez. De quantas formas distintas pode chegar ao topo? (Dica: a resposta é `F(n+1)`.) 4. **Ladrilhamento 2xN**: De quantas maneiras podemos preencher um retângulo 2xN com dominós 2x1? Mostre que a resposta segue a recorrência de Fibonacci. ## Veja Também - [Vec — Vetores dinâmicos](/stdlib/vec/) — estrutura fundamental para tabulação em DP - [HashMap — Tabelas hash](/stdlib/hashmap/) — usada para memoização com chaves arbitrárias - [Iterator — Iteradores em Rust](/stdlib/iterator/) — padrão funcional para sequências - [Otimização de Performance](/artigos/otimizacao-performance/) — técnicas gerais de otimização em Rust - [Problema da Mochila (Knapsack)](/algoritmos/knapsack/) — próximo problema clássico de DP - [Problema do Troco de Moedas](/algoritmos/coin-change/) — outra aplicação direta de DP com recorrência similar