Equipe Rust Brasil 8 min de leitura

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.

programação dinâmica fibonacci memoização tabulação rust

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)
00
11
55
1055
5012586269025

Abordagem Ingênua (Força Bruta)

A tradução direta da definição matemática gera uma função recursiva pura:

/// 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

AbordagemTempoEspaçoObservação
Força Bruta (recursão)O(2^n)O(n) pilhaImpraticável para n > 40
Top-Down (Memoização)O(n)O(n) cache + pilhaRisco de stack overflow para n grande
Bottom-Up (Tabulação)O(n)O(n) vetorIterativo, 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.

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, u64>) -> 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:

/// Memoização com Vec — acesso O(1) em vez de O(1) amortizado do HashMap.
fn fib_memo_vec(n: usize, cache: &mut Vec<Option<u64>>) -> 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:

/// 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:

/// 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:

/// 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<Self::Item> {
        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<u64> = 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):

/// 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<u64> {
    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::<u64>());
    // 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