// Fibonacci de cuatro formas: la recursión directa, con memoización, con tabla y con dos variables.
// F(0) = 0, F(1) = 1. Con long long alcanza hasta F(92).
#pragma once

#include <cstddef>
#include <vector>

// Cuenta en calls cada llamada, y en times[k] cuántas veces se calculó F(k).
inline long long fib_plain(int n, long long& calls, std::vector<long long>& times) {
    calls++;
    times[static_cast<std::size_t>(n)]++;
    if (n < 2) return n;
    return fib_plain(n - 1, calls, times) + fib_plain(n - 2, calls, times);
}

// memo[k] = -1 significa que F(k) todavía no se calcula.
inline long long fib_memo(int n, std::vector<long long>& memo, long long& calls) {
    calls++;
    if (n < 2) return n;
    const std::size_t k = static_cast<std::size_t>(n);
    if (memo[k] < 0) {
        memo[k] = fib_memo(n - 1, memo, calls) + fib_memo(n - 2, memo, calls);
    }
    return memo[k];
}

// La misma recurrencia, de los casos pequeños a los grandes. No hay llamadas recursivas.
inline long long fib_table(int n) {
    std::vector<long long> table(static_cast<std::size_t>(n) + 2, 0);
    table[1] = 1;
    for (std::size_t k = 2; k <= static_cast<std::size_t>(n); k++) {
        table[k] = table[k - 1] + table[k - 2];
    }
    return table[static_cast<std::size_t>(n)];
}

// Cada casilla solo lee las dos anteriores, así que basta guardar esas dos.
inline long long fib_two_vars(int n) {
    long long previous = 1;  // F(-1), que se define como 1 para que la suma cuadre
    long long current = 0;   // F(0)
    for (int k = 1; k <= n; k++) {
        const long long next = previous + current;
        previous = current;
        current = next;
    }
    return current;
}