El problema consiste en determinar la cantidad de formas distintas en las que una persona puede ascender una escalera de N peldaños. Las reglas de movimiento permiten avanzar είτε un escalón είτε dos escalones en cada paso. El objetivo es calcular el total de combinaciones posibles para alcanzar la cima.

Modelo Matemático

Este escenario sigue una relación de recurrencia idéntica a la sucesión de Fibonacci. Si nos encontramos en el escalón n, podemos haber llegado desde el escalón n-1 (dando un paso) o desde el n-2 (dando un salto de dos). Por lo tanto, el número de formas para llegar a n es la suma de las formas para llegar a los dos anteriores:

F(n) = F(n-1) + F(n-2)

Los casos base se definen como F(0) = 1 y F(1) = 1.

Enfoque 1: Solución Recursiva

La implementación directa utiliza una función que se llama a sí misma para resolver subproblemas más pequeños. Aunque es intuitiva, esta方法 tiene una complejidad exponencial si no se optimiza con memorización, pero es suficiente para valores pequeños de N.

#include <iostream>
using namespace std;

// Función para calcular las combinaciones recursivamente
int calcularRutas(int n) {
    // Casos base: 0 o 1 escalón tienen una única forma
    if (n < 2) {
        return 1;
    }
    // Llamada recursiva para los pasos anteriores
    return calcularRutas(n - 1) + calcularRutas(n - 2);
}

int main() {
    int entrada;
    // Lectura continua hasta el fin del flujo
    while (cin >> entrada) {
        cout << calcularRutas(entrada) << endl;
    }
    return 0;
}

Enfoque 2: Programación Dinámica Iterativa

Para evitar la redundancia de cálculos en la recursión, se puede utilizar un enfoque bottom-up. Se almacenan los rseultados intermedios en un arreglo o vector, calculando cada valor una única vez basado en los anteriores. Esto reduce la complejidad temporal a lineal.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // Tamaño máximo según las restricciones del problema
    const int LIMITE = 35;
    vector<int> memo(LIMITE);
    
    // Inicialización de casos base
    memo[0] = 1;
    memo[1] = 1;
    
    // Precomputación de valores hasta el límite
    for (int i = 2; i < LIMITE; ++i) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    
    int n;
    while (cin >> n) {
        cout << memo[n] << endl;
    }
    return 0;
}

Enfoque 3: Aritmética de Precisión Arbitraria

Cuando el número de escalones aumenta significativamente (por ejemplo, N > 90), el resultado excede la capacidad de los tipos de datos enteros estándar (long long). En tales casos, es necesario implementar una suma de grandes números utilizando cadenas de texto o vectores de dígitos.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

// Función para sumar dos números representados como cadenas
string sumarGrandesNumeros(string num1, string num2) {
    string resultado = "";
    int carry = 0;
    int i = num1.length() - 1;
    int j = num2.length() - 1;
    
    while (i >= 0 || j >= 0 || carry) {
        int suma = carry;
        if (i >= 0) suma += num1[i--] - '0';
        if (j >= 0) suma += num2[j--] - '0';
        
        carry = suma / 10;
        resultado += to_string(suma % 10);
    }
    
    reverse(resultado.begin(), resultado.end());
    return resultado;
}

int main() {
    int n;
    while (cin >> n) {
        vector<string> dp(n + 2);
        dp[0] = "1";
        dp[1] = "1";
        
        for (int k = 2; k <= n; ++k) {
            dp[k] = sumarGrandesNumeros(dp[k - 1], dp[k - 2]);
        }
        
        cout << dp[n] << endl;
    }
    return 0;
}