Uno de los ejemplos más sencillos (más que los vistos en clase) de aplicación de la programación dinámica es el cálculo del término n-ésimo de la sucesión de Fibonacci.

La definición de la sucesión o función de Fibonacci es:

Fib(n) = 1, si n = 0,1

Fib(n) = Fib(n-1) + Fib(n-2), si n > 1

La solución más natural para calcular el término n-ésimo sería, por tanto, traducir esa definición recursiva de la función a nuestro pseudocódigo:

  función FibRec(n:natural) devuelve natural
  principio
    si n≤1 entonces
      devuelve 1
    sino
      devuelve FibRec(n-1)+FibRec(n-2)
    fsi
  fin

El inconveniente de esa solución es su coste, exponencial en el valor de n. La ineficiencia de FibRec se debe a que se producen llamadas repetidas de la función para calcular valores que ya se habían calculado previamente, no se ha conservado su resultado, y por tanto hay que volver a calcularlos.

La solución de programación dinámica pasaría por utilizar una tabla auxiliar en la que almacenar las soluciones de todos los “subproblemas” (valores de Fib para valores menores que n) resueltos:

El algoritmo iterativo para devolver el n-ésimo término de Fibonacci calculando la tabla sería:

  función FibIterProto(n:natural) devuelve natural
  variables i:natural; T:vector[0..n] de natural
  principio
    si n≤1 entonces
      devuelve 1
    sino
      T[0]:=1;
      T[1]:=1;
      para i:=2 hasta n hacer
        T[i]:=T[i-1]+T[i-2]
      fpara;
      devuelve T[n]
    fsi
  fin 

El último paso en la mejora proviene de detectar que en el algoritmo anterior no es necesario todo el vector auxiliar, pues basta con almacenar los dos últimos valores calculados:

  función FibIter(n:natural) devuelve natural
  variables i,suma,x,y:natural {x e y para almacenar los dos últimos
                 términos calculados y suma para almacenar el actual}
  principio
    si n≤1 entonces
      devuelve 1
    sino
      x:=1;
      y:=1;
      para i:=2 hasta n hacer
        suma:=x+y;
        y:=x;
        x:=suma
      fpara;
      devuelve suma
    fsi
  fin