Climbing Stairs

Q: ¿Por qué subir escaleras es un problema de Fibonacci?

Cada ascenso hasta el escalón n termina con un paso de 1 desde n-1 o un paso de 2 desde n-2 , así que ways(n) = ways(n-1) + ways(n-2) . Esa es la regla de Fibonacci. Con ways(1) = 1 y ways(2) = 2 , los recuentos son 1, 2, 3, 5, 8, 13, que es la secuencia de Fibonacci desplazada un lugar: ways(n) = F(n+1) .

Q: ¿Cuál es la complejidad temporal de Climbing Stairs?

El bucle de abajo hacia arriba realiza n-2 sumas, así que se ejecuta en tiempo O(n) y usa O(1) de espacio adicional. La recursión simple es exponencial: el número de llamadas crece en un factor de aproximadamente 1.618 por paso y alcanza 2269806339, aproximadamente 2.3 × 10^9 , con n = 45 . La memoización reduce la recursión a un tiempo de O(n) y un espacio de O(n) .

Q: ¿Cómo se resuelve el problema de subir escaleras con pasos de 1, 2 o 3?

Vuelve a dividir las escaladas según su último movimiento: ways(n) = ways(n-1) + ways(n-2) + ways(n-3) . Empieza con ways(0) = 1 (la escalada vacía), ways(1) = 1 y ways(2) = 2 , y conserva los tres últimos recuentos en lugar de dos. El tiempo sigue siendo O(n) y el espacio, O(1) .

FácilProgramación dinámica Recursión

+10

Estás al pie de una escalera con n escalones. Cada movimiento sube 1 o 2 escalones. Dos ascensos cuentan como diferentes cuando sus secuencias de movimientos son distintas, así que 1, 2 y 2, 1 son dos maneras. Tu función recibe n y devuelve el número de maneras distintas de llegar a la cima.

Función

climbStairs(n: integer) → integer

ninteger: el número de escalones de la escalera
Devuelveinteger: el número de secuencias distintas de pasos de 1 y 2 que llegan al paso n

Restricciones

1 ≤ n ≤ 45
La respuesta cabe en un entero con signo de 32 bits: n = 45 da 1836311903.

Ejemplos

Entrada: n = 3
Salida: 3
Explicación: Se pueden subir tres escalones de 1, 1, 1, de 1, 2 o de 2, 1, así que hay 3 maneras.

Entrada: n = 5
Salida: 8
Explicación: Cada subida hasta el escalón 5 termina con un paso de 1 desde el escalón 4 (5 maneras de llegar) o un paso de 2 desde el escalón 3 (3 maneras), así que la respuesta es 5 + 3 = 8.

+13 pruebas ocultas al enviar

Para ir más allá

¿Qué pasa si algunos escalones están rotos y quizá nunca puedas pisarlos? ¿Cómo cambia la recurrencia y cuál es el conteo para un escalón roto?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Enumerar cada forma de subir no funciona: una escalera de 45 escalones tiene 1836311903. El último paso es la clave. Cada forma de subir hasta el escalón n pasa por el escalón n-1 o por el escalón n-2 justo antes del final, lo que da ways(n) = ways(n-1) + ways(n-2), la recurrencia de Fibonacci. Calcúlala desde abajo y solo necesitas dos variables.

Recursión simple en el último movimiento

Correcto, pero no termina con las pruebas más grandes

Intuición

Divide las subidas hasta el escalón n según su último paso. Una subida que termina con un paso de 1 se encontraba en el escalón n-1 antes de ese paso, y hay ways(n-1) subidas de ese tipo. Una subida que termina con un paso de 2 se encontraba en el escalón n-2, y hay ways(n-2) de ese tipo. Todas las subidas terminan de una forma u otra, y ninguna termina de ambas formas, así que ways(n) = ways(n-1) + ways(n-2).

La recursión necesita dos casos base. Un escalón tiene una subida, y dos escalones tienen dos subidas (1, 1 y 2). En ambos casos, la respuesta es igual a n, así que la función devuelve n cuando n ≤ 2 y, en caso contrario, la suma.

La respuesta es correcta, pero el trabajo se dispara. climbStairs(5) solicita el escalón 3 dos veces y el escalón 2 tres veces: 9 llamadas en total; el número de llamadas crece como las propias respuestas. Para n = 45, la función realiza 2269806339 llamadas, aproximadamente 2.3 × 10^9, demasiadas para un límite de tiempo. La recursión tiene solo n niveles de profundidad, así que la pila usa O(n) espacio.

Algoritmo

Si n ≤ 2, devuelve n.
Cuenta las subidas que llegan al escalón n-1 con una llamada recursiva.
Cuenta las subidas que llegan al escalón n-2 con una segunda llamada recursiva.
Devuelve la suma de los dos recuentos.

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

Recursión con un memo

Intuición

La recursión solo es lenta porque olvida. Cada conteo depende únicamente de k, así que, una vez que conoces el conteo para el paso k, nunca cambia. Guarda una memo, un arreglo con una posición por paso, y escribe cada conteo ahí la primera vez que lo calculas. Cada solicitud posterior del mismo paso lee la posición en lugar de volver a recurrir.

Ahora, cada uno de los conteos desde el paso 3 hasta el paso n se calcula una vez, con una suma. Para n = 5, las llamadas llegan hasta el paso 2 una vez; después, las respuestas vuelven como 3, 5 y 8, y la segunda solicitud del paso 3 es una consulta. Eso es tiempo O(n) en lugar de miles de millones de llamadas.

La memo contiene n + 1 números y la recursión sigue teniendo n niveles de profundidad, así que el espacio es O(n). Un 0 en una posición significa que aún no se conoce el valor, lo cual es seguro porque cada conteo real es al menos 1.

Algoritmo

Crea una memo con n + 1 espacios, todos en 0.
En la función auxiliar recursiva, devuelve k cuando k ≤ 2.
Si el espacio de la memo para k es 0, rellénalo con la suma de los resultados de la función auxiliar para k-1 y k-2.
Devuelve el espacio de la memo.
Llama a la función auxiliar con 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 abajo hacia arriba con dos variables

Intuición

Invierte la recursión. En lugar de empezar por arriba y avanzar hacia abajo, empieza por abajo y construye hacia arriba. Cuando calculas el conteo para el paso k, ya conoces los conteos para k-1 y k-2, y nunca vuelves a leer ningún valor anterior. Así que dos variables sustituyen toda la memoria.

Haz que prev contenga el conteo para el paso k-2 y que curr contenga el conteo para el paso k-1. Empieza con prev = 1 y curr = 2, los conteos para los pasos 1 y 2. En cada paso, súmalos en next y después avanza el par. Para n = 5, el par pasa de (1, 2) a (2, 3), (3, 5) y (5, 8), y curr = 8 es la respuesta.

El bucle se ejecuta n-2 veces con una suma cada vez, tiempo O(n), y mantiene tres enteros, espacio O(1). Calcula next antes de sobrescribir prev, o la suma usará el valor equivocado.

Algoritmo

Si n ≤ 2, devuelve n.
Establece prev = 1 y curr = 2.
Para k desde 3 hasta n, calcula next = prev + curr, después establece prev = curr y curr = next.
Devuelve 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

Errores comunes y casos límite

La recurrencia es breve, así que la mayoría de los errores se encuentran en los casos base, el tiempo de ejecución y el límite de 32 bits.

Entregar la recursión simple. Supera las pruebas pequeñas y después necesita unas 2.3 × 10^9 llamadas para n = 45. Almacena cada conteo una sola vez.
Casos base incorrectos. Para dos escalones hay dos formas de subir: 1, 1 y 2. Devolver 1 para n = 2 desplaza todas las respuestas posteriores: obtendrías 2 para n = 3 en lugar de 3.
Contar las opciones en lugar de las secuencias. 1, 2 y 2, 1 son dos formas de subir. Contar solo cuántos pasos de 2 das da n/2 + 1, que es 3 para n = 5 en lugar de 8.
Rellenar una tabla sin una comprobación previa. Con n = 1, una tabla de n + 1 = 2 posiciones no tiene espacio para el conteo del escalón 2. Devuelve n de inmediato cuando n ≤ 2.
Avanzar un paso de más. El conteo para 45 escalones, 1836311903, cabe en 32 bits, pero el conteo para 46 escalones es 2971215073 y no cabe. Un bucle que calcula un valor adicional se desborda y da un número negativo en Java, C o C#.

Preguntas frecuentes4

¿Por qué subir escaleras es un problema de Fibonacci?

Cada ascenso hasta el escalón n termina con un paso de 1 desde n-1 o un paso de 2 desde n-2, así que ways(n) = ways(n-1) + ways(n-2). Esa es la regla de Fibonacci. Con ways(1) = 1 y ways(2) = 2, los recuentos son 1, 2, 3, 5, 8, 13, que es la secuencia de Fibonacci desplazada un lugar: ways(n) = F(n+1).

¿Cuál es la complejidad temporal de Climbing Stairs?

El bucle de abajo hacia arriba realiza n-2 sumas, así que se ejecuta en tiempo O(n) y usa O(1) de espacio adicional. La recursión simple es exponencial: el número de llamadas crece en un factor de aproximadamente 1.618 por paso y alcanza 2269806339, aproximadamente 2.3 × 10^9, con n = 45. La memoización reduce la recursión a un tiempo de O(n) y un espacio de O(n).

¿Cuál es la diferencia entre la memorización y la solución ascendente?

La memoización conserva la función recursiva y almacena en caché cada resultado la primera vez que se calcula, por lo que funciona de arriba abajo y necesita la pila de llamadas y una tabla. El bucle de abajo arriba calcula las cantidades en orden creciente, así que todos los valores que necesita ya se conocen y no interviene ninguna recursión. Ambos realizan un trabajo de O(n). El bucle también te permite prescindir de la tabla y conservar dos números.

¿Cómo se resuelve el problema de subir escaleras con pasos de 1, 2 o 3?

Vuelve a dividir las escaladas según su último movimiento: ways(n) = ways(n-1) + ways(n-2) + ways(n-3). Empieza con ways(0) = 1 (la escalada vacía), ways(1) = 1 y ways(2) = 2, y conserva los tres últimos recuentos en lugar de dos. El tiempo sigue siendo O(n) y el espacio, O(1).

Python

def climbStairs(n):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Entrada

n = 3

Esperado

Climbing Stairs

Función

Restricciones

Ejemplos

Pistas

Solución

Recursión simple en el último movimiento

Recursión con un memo

De abajo hacia arriba con dos variables

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares