Fibonacci par table

Exercice · OCaml (option informatique), chapitre 13 — Programmation dynamique

Énoncé

Écrire fibo n en remplissant un tableau (bas-haut), en $Θ (n)$ .

Corrigé

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 $Θ (n)$ , contre exponentiel pour la double récursion naïve.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.