Fibonacci - Dynamic Programming.

[GGZ]

Quiero escribir esto:

Código (c) [Seleccionar] Expandir

int fib (int n){
       if (n <= 1)
               return n;
       return fib(n-1) + fib(n-2);
}


En programación dinámica es decir sin que se recalculen tantas veces los mismos resultados y usando TOP-DOWN.

Intenté esto:

Código (c) [Seleccionar] Expandir


#define MAX 1000
char mem[MAX];

void start(){
       int i;
       for (i=0; i<MAX; i++)
               mem[i] = -1;
}

int td (int n){

       // Si es igual a -1 significa que todavía no lo resolvimos.
       if (mem[n] == -1){

               if (n <= 1)
                       mem[n] = n;
               else
                       mem[n] = td(n-1) + td(n-2);
       }

       return mem[n];
}


Pero no funciona funciona en los primeros a partir del número 20 tira mal el resultado, ¿alguna pista de por qué no funciona?

Saludos.

[ivancea96]

Pusiste la matriz como char:

Código (c) [Seleccionar] Expandir

char mem[MAX];

Un char va de -128 a 127, así que da overflows.

Querrías ponerla como int:

Código (c) [Seleccionar] Expandir

int mem[MAX];

[GGZ]

Estaba distraído mientras lo programaba, cómo se me pasó eso?, hubiera estado horas buscando el problema en otra parte.

Gracias.