Climbing Stairs

Q: Por que subir escadas é um problema de Fibonacci?

Toda subida até o degrau n termina com um passo de 1 degrau a partir de n-1 ou com um passo de 2 degraus a partir de n-2 , então ways(n) = ways(n-1) + ways(n-2) . Essa é a regra de Fibonacci. Com ways(1) = 1 e ways(2) = 2 , as contagens são 1, 2, 3, 5, 8, 13, que é a sequência de Fibonacci deslocada uma posição: ways(n) = F(n+1) .

Q: Qual é a complexidade de tempo do problema de subir escadas?

O loop de baixo para cima faz n-2 adições, então é executado em tempo O(n) e usa espaço extra O(1) . A recursão simples é exponencial: o número de chamadas cresce por um fator de cerca de 1.618 a cada passo e chega a 2269806339, aproximadamente 2.3 × 10^9 , em n = 45 . A memoização reduz a recursão para tempo O(n) e espaço O(n) .

FácilProgramação dinâmica Recursão

+10

Você está no início de uma escada com n degraus. A cada movimento, sobe 1 ou 2 degraus. Duas subidas são consideradas diferentes quando suas sequências de movimentos diferem, então 1, 2 e 2, 1 são duas maneiras. Sua função recebe n e retorna o número de maneiras distintas de chegar ao topo.

Função

climbStairs(n: integer) → integer

ninteger: o número de degraus na escada
Retornainteger: o número de sequências distintas de passos de 1 e 2 que chegam ao passo n

Restrições

1 ≤ n ≤ 45
A resposta cabe em um inteiro de 32 bits com sinal: n = 45 resulta em 1836311903.

Exemplos

Entrada: n = 3
Saída: 3
Explicação: Três degraus podem ser subidos como 1, 1, 1, como 1, 2 ou como 2, 1, então há 3 maneiras.

Entrada: n = 5
Saída: 8
Explicação: Todo caminho até o degrau 5 termina com um passo de 1 a partir do degrau 4 (5 maneiras de chegar lá) ou um passo de 2 a partir do degrau 3 (3 maneiras), então a resposta é 5 + 3 = 8.

+13 testes ocultos ao enviar

Para ir além

O que acontece se alguns degraus estiverem quebrados e você talvez nunca pise neles? Como a recorrência muda e qual é a contagem para um degrau quebrado?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Listar cada subida não funciona: uma escada de 45 degraus tem 1836311903 maneiras de subi-la. A chave está no último movimento. Toda subida até o degrau n passa pelo degrau n-1 ou pelo degrau n-2 logo antes do fim, o que resulta em ways(n) = ways(n-1) + ways(n-2), a recorrência de Fibonacci. Calcule de baixo para cima, e duas variáveis são tudo de que você precisa.

Recursão simples no último movimento

Correta, mas não termina nos maiores testes

Intuição

Divida as formas de subir até o degrau n de acordo com o último movimento. Uma subida que termina com um passo de 1 degrau estava no degrau n-1 antes dele, e há ways(n-1) subidas desse tipo. Uma subida que termina com um passo de 2 degraus estava no degrau n-2, e há ways(n-2) dessas. Toda subida termina de uma forma ou de outra, e nenhuma termina das duas formas, então ways(n) = ways(n-1) + ways(n-2).

A recursão precisa de dois casos-base. Um degrau tem uma forma de subir, e dois degraus têm duas formas (1, 1 e 2). Nos dois casos, a resposta é igual a n, então a função retorna n quando n ≤ 2 e, caso contrário, retorna a soma.

A resposta está certa, mas o trabalho explode. climbStairs(5) calcula o degrau 3 duas vezes e o degrau 2 três vezes, totalizando 9 chamadas, e a quantidade de chamadas cresce como as próprias respostas. Para n = 45, a função faz 2269806339 chamadas, cerca de 2.3 × 10^9, muito acima do limite de tempo. A recursão tem apenas n níveis de profundidade, então a pilha usa O(n) de espaço.

Algoritmo

Se n ≤ 2, retorne n.
Conte as subidas que chegam ao degrau n-1 com uma chamada recursiva.
Conte as subidas que chegam ao degrau n-2 com uma segunda chamada recursiva.
Retorne a soma das duas contagens.

def climbStairs(n):
    if n <= 2:
        return n  # 1 step: one way, 2 steps: two ways
    return climbStairs(n - 1) + climbStairs(n - 2)

Recursão com memoização

Intuição

A recursão é lenta apenas porque se esquece. Cada contagem depende apenas de k, então, depois que você sabe a contagem da etapa k, ela nunca muda. Mantenha uma memória, um array com um espaço por etapa, e grave cada contagem ali na primeira vez que a calcular. Toda solicitação posterior da mesma etapa lê o espaço em vez de recursar novamente.

Agora, cada uma das contagens da etapa 3 até a etapa n é calculada uma vez, com uma adição. Para n = 5, as chamadas descem até a etapa 2 uma vez; então, as respostas voltam como 3, 5 e 8, e a segunda solicitação da etapa 3 é uma consulta. Isso é tempo O(n) em vez de bilhões de chamadas.

A memória mantém n + 1 números, e a recursão ainda tem n níveis de profundidade, então o espaço é O(n). Um 0 em um espaço significa que o valor ainda não é conhecido, o que é seguro porque toda contagem real é pelo menos 1.

Algoritmo

Crie uma tabela de memoização com n + 1 posições, todas com 0.
Na função auxiliar recursiva, retorne k quando k ≤ 2.
Se a posição da tabela de memoização para k for 0, preencha-a com a soma dos resultados da função auxiliar para k-1 e k-2.
Retorne a posição da tabela de memoização.
Chame a função auxiliar com n.

def climbStairs(n):
    memo = [0] * (n + 1)  # memo[k] = ways to reach step k, 0 = not known yet

    def ways(k):
        if k <= 2:
            return k
        if memo[k] == 0:
            memo[k] = ways(k - 1) + ways(k - 2)
        return memo[k]

    return ways(n)

De baixo para cima com duas variáveis

Intuição

Inverta a recursão. Em vez de começar do topo e perguntar para baixo, comece da base e construa para cima. Quando você calcula a contagem para a etapa k, as contagens de k-1 e k-2 já são conhecidas, e nada mais antigo é lido novamente. Assim, duas variáveis substituem toda a memoização.

Deixe prev armazenar a contagem da etapa k-2 e curr, a contagem da etapa k-1. Comece com prev = 1 e curr = 2, as contagens das etapas 1 e 2. A cada etapa, some os valores em next e, em seguida, avance o par. Para n = 5, o par passa de (1, 2) para (2, 3), (3, 5) e (5, 8), e curr = 8 é a resposta.

O loop é executado n-2 vezes, com uma adição em cada iteração, levando tempo O(n) e mantendo três números inteiros, com espaço O(1). Calcule next antes de sobrescrever prev, ou a soma usará o valor errado.

Algoritmo

Se n ≤ 2, retorne n.
Defina prev = 1 e curr = 2.
Para k de 3 até n, calcule next = prev + curr, depois defina prev = curr e curr = next.
Retorne curr.

def climbStairs(n):
    if n <= 2:
        return n
    prev, curr = 1, 2  # ways to reach steps 1 and 2
    for _ in range(n - 2):
        prev, curr = curr, prev + curr
    return curr

Armadilhas e casos extremos

A recorrência é curta, então a maioria dos bugs está nos casos-base, no tempo de execução e no limite de 32 bits.

Entregar a recursão simples. Ela passa nos testes pequenos, mas depois precisa de cerca de 2.3 × 10^9 chamadas para n = 45. Armazene cada contagem uma única vez.
Casos-base incorretos. Há duas maneiras de subir dois degraus: 1, 1 e 2. Retornar 1 para n = 2 desloca todas as respostas seguintes: você obteria 2 para n = 3 em vez de 3.
Contar escolhas em vez de sequências. 1, 2 e 2, 1 são duas maneiras de subir. Contar apenas quantos passos de 2 você dá resulta em n/2 + 1, que é 3 para n = 5 em vez de 8.
Preencher uma tabela sem uma verificação. Com n = 1, uma tabela de n + 1 = 2 posições não tem espaço para a contagem do degrau 2. Retorne n imediatamente quando n ≤ 2.
Executar um passo a mais. A contagem para 45 degraus, 1836311903, cabe em 32 bits, mas a contagem para 46 degraus é 2971215073 e não cabe. Um loop que calcula um valor extra causa um overflow para um número negativo em Java, C ou C#.

Perguntas frequentes4

Por que subir escadas é um problema de Fibonacci?

Toda subida até o degrau n termina com um passo de 1 degrau a partir de n-1 ou com um passo de 2 degraus a partir de n-2, então ways(n) = ways(n-1) + ways(n-2). Essa é a regra de Fibonacci. Com ways(1) = 1 e ways(2) = 2, as contagens são 1, 2, 3, 5, 8, 13, que é a sequência de Fibonacci deslocada uma posição: ways(n) = F(n+1).

Qual é a complexidade de tempo do problema de subir escadas?

O loop de baixo para cima faz n-2 adições, então é executado em tempo O(n) e usa espaço extra O(1). A recursão simples é exponencial: o número de chamadas cresce por um fator de cerca de 1.618 a cada passo e chega a 2269806339, aproximadamente 2.3 × 10^9, em n = 45. A memoização reduz a recursão para tempo O(n) e espaço O(n).

Qual é a diferença entre memoização e a solução de baixo para cima?

A memoização mantém a função recursiva e armazena em cache cada resultado na primeira vez em que ele é calculado, então funciona de cima para baixo e precisa da pilha de chamadas e de uma tabela. O loop de baixo para cima calcula as contagens em ordem crescente, então todos os valores de que precisa já são conhecidos e não há recursão envolvida. Ambos fazem O(n) de trabalho. O loop também permite descartar a tabela e manter dois números.

Como resolver o problema de subir escadas com passos de 1, 2 ou 3?

Divida as subidas de acordo com o último movimento novamente: ways(n) = ways(n-1) + ways(n-2) + ways(n-3). Comece com ways(0) = 1 (a subida vazia), ways(1) = 1 e ways(2) = 2, e mantenha as últimas três contagens em vez de duas. O tempo continua sendo O(n) e o espaço, O(1).

Python

def climbStairs(n):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Entrada

n = 3

Esperado

Climbing Stairs

Função

Restrições

Exemplos

Dicas

Solução

Recursão simples no último movimento

Recursão com memoização

De baixo para cima com duas variáveis

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos