Fibonacci par table

let fibo n =
  if n <= 1 then n
  else begin
    let dp = Array.make (n + 1) 0 in
    dp.(1) <- 1;
    for i = 2 to n do dp.(i) <- dp.(i - 1) + dp.(i - 2) done;
    dp.(n)
  end

Chaque dp.(i) est calculé une fois à partir des deux précédents : c'est la version bas-haut de la mémoïsation du chapitre 8. Coût $\Theta (n)$, contre exponentiel pour la double récursion naïve.