Ejercicio de codificación – Subir escaleras – Números de Fibonacci – C++ – Juez en línea

Pregunta: Estás subiendo escaleras. Se necesitan n pasos para llegar a la cima. Cada vez, puede dar 1 paso o 2 pasos. ¿Cuántas maneras distintas de llegar a la cima?

Descripción del problema: http://oj.leetcode.com/problems/climbing-stairs/

Este problema puede parecer difícil al principio, pero cuando piensas por un segundo, puede que te resulte muy fácil. La respuesta es Números de Fibonacci (ver aquí, aquí )

Bueno, los números de Fibonacci originales se definen como secuencias:

Para este problema, solo tenemos que modificar un poco:

y porque para solo 1 paso, solo hay 1 manera distinta y para 2 pasos, tenemos dos soluciones: 1 + 1 o 2.

El resto es como serie de Fibonacci. El porque desde la posición actual, posiblemente estemos desde las dos posiciones anteriores, F(n-1) y F(n-2).

Puede usar la recursividad, pero esto se puede resolver mediante una solución iterativa más efectiva.

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        // f(n) = f(n - 1) + f(n - 2)
        int a = 1, b = 2, c = a + b;
        for (int i = 3; i <= n; i ++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
};

O prefiere una función recursiva más directa:

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: La recursiva producirá TIME LIMIT EXCEEDED en la prueba 44. Esto se debe a que la función recursiva generalmente calcula valores intermedios muchas veces. Por ejemplo, , .  se calcula dos veces.