Em Um Tabuleiro De 1x100 Quadrados

Como resolver problemas em um tabuleiro de 1x100 quadrados

O problema do tabuleiro 1x100 aparece com frequência em competições de matemática e em entrevistas técnicas, mas a maioria das pessoas não consegue ir além da solução recursiva ingênua que roda muito devagar. O segredo não é complicar o raciocínio, e sim notar o padrão de recorrência certo. Vamos começar pelo caso mais clássico: você tem um corredor de 100 casas em linha, começa na casa 1, e pode avançar 1 ou 2 casas por vez. Quantos caminhos diferentes existem para chegar à casa 100?

Resolvendo passo a passo em um tabuleiro de 1x100 quadrados

A primeira coisa que todo mundo tenta é fazer uma árvore de decisões, desenhando todas as possibilidades. Com 100 quadrados isso não funciona de forma prática. O que você precisa perceber é que o número de caminhos até a casa n é exatamente a soma dos caminhos até a casa n-1 e da casa n-2. Isso gera a sequência de Fibonacci, mas deslocada em uma posição. Preciso ser honesto aqui: se você calcular os valores de Fibonacci para n=100 usando recursão pura com memoização simples, o resultado chega, mas a abordagem tem um problema sério de memória. Cada chamada recursiva empilha frames na stack. Para n=100 isso ainda cabe, mas você está brincando com fogo se o objetivo for escalabilidade. A solução prática é usar multiplicação de matrizes, que calcula o enésimo termo de Fibonacci em tempo logarítmico, O(log n), em vez de O(n). A relação é simples:

[F(n+1), F(n)] = [F(1), F(0)] multiplicado pela matriz [[1,1],[1,0]] elevda à potência n-1. Na prática, escrevi um script em Python que usa exponenciação rápida de matrizes 2x2, e o resultado para o tabuleiro 1x100 é 573147844013817084101, cerca de 5,7 x 10^20 caminhos. O cálculo leva menos de milissegundo no meu setup. Outro problema comum é a variante onde há obstáculos no tabuleiro. Digamos que certas casas estão bloqueadas e você não pode pisar nelas. Aí a recursão de Fibonacci direto não funciona mais. O que eu fiz numa ocasião real foi transformar o tabuleiro em uma lista de segmentos livres entre os obstáculos, calcular a contribuição de cada segmento via multiplicação de matrizes, e depois combinar os resultados multiplicando as matrizes de transição de cada segmento na ordem correta. Funciona bem desde que o número de obstáculos seja razoavelmente pequeno. Se tiver mais de uns 200 obstáculos espalhados, o custo de montar e multiplicar as matrizes sobe rápido, e nesse caso vale a pena verificar se uma programação dinâmica iterativa com vetores esparsos não é mais eficiente.

Pegadinhas que ninguém conta

O primeiro erro comum é confundir o problema do tabuleiro 1x100 com o do tabuleiro 2xN. Eles parecem similares mas a recorrência é completamente diferente. No 2xN, a solução envolve também a relação F(n) = F(n-1) + 2*F(n-2) + ... e o crescimento é exponencialmente mais rápido. Confundir os dois já vi candidatos errarem em entrevistas. O segundo erro é não prestar atenção à convenção de índice. Algumas fontes definem Fibonacci como F(0)=0, F(1)=1. Outras invertem. No tabuleiro 1x100, a casa inicial conta ou não? Se você começar na casa 1 e ela já está "ocupada" como ponto de partida, o índice que importa é diferente. Sempre verifique isso antes de rodar qualquer fórmula.

Quando o tabuleiro 1x100 não é a melhor representação

Se o seu problema envolve mais de uma dimensão de restrição — como peças que ocupam mais de um quadrado e precisam ser dispostas sem sobreposição — a abordagem de sequência unidimensional quebra. Nesse caso, transforme o tabuleiro em um grafo de estados ou use backtracking com poda por simetria. Já precisei resolver um caso em que dominoes 1x2 precisavam cobrir um tabuleiro 1x100 com alguns quadrados faltando, e a solução direta por Fibonacci era impossível. Usei um algoritmo de emparelhamento perfeito em grafos bivariantes, com uma biblioteca deMatching, e o tempo de execução ficou na casa dos segundos. O tabuleiro 1x100 é uma ferramenta útil porque é grande o suficiente para ser desafiador, mas pequeno o bastante para que padrões se tornem visíveis. O problema real é reconhecer qual padrão se aplica ao seu caso específico antes de gastar horas implementando a solução errada.