24 de Março
Subindo escadas
Como perceber a recorrencia pelas ultimas duas escolhas e usar isso como porta de entrada para programação dinamica.
Programação Dinamica Iniciante 15 min TypeScript
Você esta subindo uma escada. Para chegar ao topo com n degraus, pode subir 1 ou 2 degraus por vez.
Retorne quantas formas distintas existem para chegar ao topo.
Exemplo:
Input: n = 3
Output: 3
As formas sao: 1+1+1, 1+2, 2+1.
O que perceber antes de codar
- O problema pede quantidade de formas, não o menor número de passos.
- Para chegar ao degrau atual, o ultimo salto só pode ser de 1 ou 2.
- Os mesmos subproblemas aparecem várias vezes se você usar recursão pura.
Erros comuns
- confundir o problema com minimização de passos
- errar os casos base para `n = 1` e `n = 2`
Passo 1 — Perguntar de onde o ultimo passo pode ter vindo
Para chegar no degrau n, o ultimo movimento só pode ser:
- de
n - 1paran - de
n - 2paran
Não existe terceira opcao.
Isso já sugere que o número de formas de chegar em n depende dos dois casos anteriores.
Passo 2 — Escrever a versão inicial recursiva
A primeira ideia correta costuma ser:
export function climbStairs(n: number): number {
if (n <= 2) {
return n
}
return climbStairs(n - 1) + climbStairs(n - 2)
}
Funciona. Mas repete muito trabalho.
Para calcular climbStairs(5), você recalcula climbStairs(3) mais de uma vez, por exemplo.
Passo 3 — Identificar a recorrencia
A relação central e:
ways(n) = ways(n - 1) + ways(n - 2)
Porque toda forma de chegar em n termina vindo de um desses dois degraus.
Passo 4 — Guardar só o que realmente importa
Você não precisa manter a árvore inteira da recursão.
Só precisa saber:
- quantas formas chegam no degrau anterior
- quantas formas chegam em dois degraus antes
O resto vai sendo descartado.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function climbStairs(n: number): number {
// sua solução aqui
return 0
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(n)
Espaço: O(1)
Solução 1 — Recursao pura antes de memoization
Boa para enxergar a ideia, ruim para escalar.
export function climbStairs(n: number): number {
if (n <= 2) {
return n
}
return climbStairs(n - 1) + climbStairs(n - 2)
}O problema aqui não e a formula. E o retrabalho.
Solução 2 — Programacao dinamica com estado reduzido em espaco O(1)
Agora a mesma recorrencia roda de forma iterativa.
export function climbStairs(n: number): number {
if (n <= 2) {
return n
}
let twoStepsBefore = 1
let oneStepBefore = 2
for (let stair = 3; stair <= n; stair += 1) {
const current = oneStepBefore + twoStepsBefore
twoStepsBefore = oneStepBefore
oneStepBefore = current
}
return oneStepBefore
}Você mantem só o estado necessário para calcular o próximo degrau.
O que dizer na entrevista
Uma explicação curta e boa seria:
Para chegar no degrau
n, o ultimo passo só pode ter vindo den - 1oun - 2. Isso gera a recorrenciaf(n) = f(n - 1) + f(n - 2). A recursão pura funciona, mas recalcula subproblemas. Entao eu transformo em DP iterativa e mantenho só os dois estados anteriores.
Isso mostra que você:
- enxergou a recorrencia certa
- explicou por que a recursão pura desperdiça trabalho
- conectou DP a uma necessidade concreta
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- contar formas de chegar a um estado
- montar resposta a partir de poucos estados anteriores
- trocar
recursaorepetitiva porprogramacao dinamicalinear - reconhecer subproblemas repetidos cedo
O ponto não e decorar “isso parece Fibonacci”.
O ponto e justificar de onde a recorrencia vem.