// Fibonacci con memoización: compara las llamadas con y sin la tabla de resultados.
#include <stdio.h>
#include <stdlib.h>

#define NOT_KNOWN (-1)

long long fib(int n, long long *calls) {
    (*calls)++;
    if (n < 2) {
        return n;
    }
    return fib(n - 1, calls) + fib(n - 2, calls);
}

// memo[n] guarda fib(n), o NOT_KNOWN si todavía no se calculó.
long long fib_memo(int n, long long memo[], long long *calls) {
    (*calls)++;
    if (n < 2) {
        return n;
    }
    if (memo[n] != NOT_KNOWN) {
        return memo[n];
    }
    memo[n] = fib_memo(n - 1, memo, calls) + fib_memo(n - 2, memo, calls);
    return memo[n];
}

// Calcula fib(n) con una tabla nueva. Devuelve -1 si no hay memoria.
long long fib_with_table(int n, long long *calls) {
    long long *memo = malloc((n + 1) * sizeof(long long));
    if (memo == NULL) {
        return -1;
    }
    for (int i = 0; i <= n; i++) {
        memo[i] = NOT_KNOWN;
    }
    long long value = fib_memo(n, memo, calls);
    free(memo);
    return value;
}

int main(void) {
    const int sizes[] = {5, 10, 20, 30, 35};
    int count = (int) (sizeof(sizes) / sizeof(sizes[0]));

    printf("%4s %12s %12s %12s\n", "n", "fib(n)", "sin tabla", "con tabla");
    for (int i = 0; i < count; i++) {
        long long plain_calls = 0;
        long long memo_calls = 0;
        long long value = fib(sizes[i], &plain_calls);
        if (fib_with_table(sizes[i], &memo_calls) != value) {
            printf("no hay memoria o los resultados no coinciden\n");
            return 1;
        }
        printf("%4d %12lld %12lld %12lld\n", sizes[i], value, plain_calls, memo_calls);
    }

    long long calls = 0;
    long long value = fib_with_table(90, &calls);
    if (value < 0) {
        printf("no hay memoria\n");
        return 1;
    }
    printf("fib(90) = %lld, con %lld llamadas\n", value, calls);
    return 0;
}