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.
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.