Fácil-medio · intro PD

Subir escaleras

Piensa en el último paso, no en el primero: para estar en el escalón n vienes de n−1 o de n−2, y esos dos viajes no comparten su último paso. Esa frase es todo el algoritmo.

En una fraseways(n) = ways(n-1) + ways(n-2), con ways(1) = 1 y ways(2) = 2 — lleva solo dos variables por la escalera.

El problema

Entrada: Un entero n (1 ≤ n ≤ 40), el número de escalones.

Salida: El número de formas distintas de llegar al escalón n dando pasos de 1 o 2.

Ejemplos:

Entrada	Salida
`3`	`3`
`5`	`8`

Para n = 3 las formas son 1+1+1, 1+2 y 2+1: el orden de los pasos cuenta, por eso 2+1 no es el mismo viaje que 1+2.

Tu solución

main.cpp — tu solución

Entrada personalizada para «Ejecutar mi entrada»

La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.

¿Atascado? Pistas

Pista 1 — Razona desde el último paso

Todo viaje al escalón n acaba con un último paso de 1 (desde n−1) o de 2 (desde n−2). Los dos grupos no se solapan y juntos son todos los viajes — así que ways(n) = ways(n-1) + ways(n-2). Cuando un argumento empieza con «mira el último paso», la programación dinámica suele estar cerca.

Pista 2 — Clava los casos base

ways(1) = 1 (una forma: 1) y ways(2) = 2 (1+1, o 2). Escríbelos antes del bucle y comprueba a mano las entradas mínimas — la mayoría de las respuestas erróneas aquí son un caso base desfasado en uno, no una recurrencia rota.

Pista 3 — Con dos variables basta

La recurrencia solo mira uno y dos pasos atrás, así que guarda a = ways(k-1) y b = ways(k) y hazlas rodar: c = a + b; a = b; b = c;. Sin array, sin recursión — y sin la explosión exponencial que sufre la versión recursiva ingenua.

Solución (¡inténtalo primero!)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    long long a = 1, b = 2;   // ways(1), ways(2)
    if (n == 1) { cout << 1 << endl; return 0; }
    for (int k = 3; k <= n; k++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    cout << b << endl;
    return 0;
}

Acabas de escribir tu primer programa dinámico: una recurrencia, casos base y un relleno de abajo hacia arriba. Las mismas tres piezas resuelven Fibonacci (son literalmente los mismos números) y más adelante tablas como Suma mínima del camino. La costumbre que vale la pena: deriva la recurrencia del último paso y confía en ella hasta abajo.

Análisis profundo

Por qué funciona

Pregunta por el último paso, no por el primero: todo viaje al escalón n llega desde n−1 (un paso de 1) o desde n−2 (un paso de 2), y esas dos familias no se solapan ni dejan huecos. Así que ways(n) = ways(n-1) + ways(n-2) — la definición de una PD donde la respuesta para n se construye con respuestas menores ya conocidas.

El coste

O(n) de tiempo y O(1) de espacio con dos variables rodantes: 40 escalones son 38 sumas. La recursión ingenua hace en cambio unas 2^n llamadas — para n = 40, más de mil millones, casi todas recálculos de los mismos valores.

Dónde falla

Casos base: ways(1) = 1 y ways(2) = 2 (el salto de dos es una forma, no dos). Sembrar el par como 1 y 1 desplaza hacia abajo todas las respuestas posteriores.
La recursión ingenua sin memoización es exponencial — un juez real agota el tiempo hacia n = 40. El par rodante es la misma matemática sin la explosión. Y a partir de n = 45 el conteo desborda un int de 32 bits: usa long long.
ways(0) = 1 (quedarte quieto) también es una convención válida — pero mezclar convenciones a mitad de código cuenta doble. Elige una y alinea tu bucle con ella.

Siguiente paso

Son los mismos números con otro abrigo: Fibonacci pide la recurrencia idéntica. La mejora a dos dimensiones de construir-una-tabla-con-vecinos es Suma mínima del camino.

Dos cosas para recordar

PD = último paso + respuestas menores; derívalo del paso final.
Dos variables rodantes sustituyen al array entero cuando la recurrencia solo mira 1–2 pasos atrás.

🐞 Esta versión falla: ábrela y pruébala

Siembra el par como 1 y 1: toda respuesta con n > 1 sale un escalón pequeña

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long a = 1, b = 1;   // bug: ways(2) should be 2
    if (n == 1) { cout << 1 << endl; return 0; }
    for (int k = 3; k <= n; k++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    cout << b << endl;
    return 0;
}