Exercício de codificação – Subindo escadas – Números de Fibonacci – C++ – Juiz Online

Pergunta: Você está subindo escadas. São necessários n passos para chegar ao topo. Cada vez, você pode dar 1 passo ou 2 passos. Quantas maneiras distintas de chegar ao topo?

Descrição do problema: http://oj.leetcode.com/problems/climbing-stairs/

Esse problema pode parecer difícil no começo, mas quando você pensa por um segundo, pode achar muito fácil. A resposta é Números de Fibonacci (veja aqui, aqui )

Bem, os Números de Fibonacci originais são definidos como sequências:

Para este problema, basta modificar um pouco:

e porque para apenas 1 passo, há apenas 1 caminho distinto e para 2 passos, temos duas soluções: 1 + 1 ou 2.

O resto é como série de Fibonacci. O porque da posição atual, possivelmente somos das duas posições anteriores, F(n-1) e F(n-2).

Você pode usar recursão, mas isso pode ser resolvido por uma solução iterativa mais eficaz.

Ou você prefere uma função recursiva mais direta:

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
};

Nota: A recursiva produzirá TIME LIMIT EXCEEDED no teste 44. Isso porque, a função recursiva normalmente calcula valores intermediários muitas e muitas vezes. Por exemplo, , .  é calculado duas vezes.