Programmation dynamique

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.

let rendu_min pieces montant =
  let infini = montant + 1 in
  let m = Array.make (montant + 1) infini in
  m.(0) <- 0;
  for s = 1 to montant do
    List.iter (fun p ->
      if p <= s && m.(s - p) + 1 < m.(s) then m.(s) <- m.(s - p) + 1
    ) pieces
  done;
  if m.(montant) = infini then -1 else m.(montant)

rendu_min [4;3;1] 6 : m.(6) se calcule via m.(3) + 1 (et m.(3) = 1), soit 2. La DP trouve l'optimum $3+3$, contrairement au glouton.

let nb_facons pieces montant =
  let dp = Array.make (montant + 1) 0 in
  dp.(0) <- 1;
  List.iter (fun p ->
    for s = p to montant do
      dp.(s) <- dp.(s) + dp.(s - p)
    done
  ) pieces;
  dp.(montant)

On traite les pièces l'une après l'autre (boucle externe sur pieces) pour ne compter chaque combinaison qu'une fois (et non chaque permutation). dp.(0) = 1 : une seule façon de rendre $0$ (ne rien donner).

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

Pour atteindre la marche i, on vient de i-1 (pas de $1$) ou de i-2 (pas de $2$) : dp.(i) = dp.(i-1) + dp.(i-2). On retrouve… la suite de Fibonacci ! Beaucoup de problèmes de comptage s'y ramènent.

let chemin_min cout =
  let n = Array.length cout and m = Array.length cout.(0) in
  let dp = Array.make_matrix n m 0 in
  dp.(0).(0) <- cout.(0).(0);
  for j = 1 to m - 1 do dp.(0).(j) <- dp.(0).(j - 1) + cout.(0).(j) done;
  for i = 1 to n - 1 do dp.(i).(0) <- dp.(i - 1).(0) + cout.(i).(0) done;
  for i = 1 to n - 1 do
    for j = 1 to m - 1 do
      let h = if dp.(i - 1).(j) <= dp.(i).(j - 1) then dp.(i - 1).(j) else dp.(i).(j - 1) in
      dp.(i).(j) <- h + cout.(i).(j)
    done
  done;
  dp.(n - 1).(m - 1)

On arrive en (i,j) par le haut ou par la gauche : on prend le moins coûteux, plus le coût de la case. La première ligne et la première colonne (un seul chemin possible) servent de cas de base. Coût $\Theta (nm)$.

let plsc a b =
  let n = String.length a and m = String.length b in
  let dp = Array.make_matrix (n + 1) (m + 1) 0 in
  for i = 1 to n do
    for j = 1 to m do
      if a.[i - 1] = b.[j - 1] then dp.(i).(j) <- dp.(i - 1).(j - 1) + 1
      else dp.(i).(j) <-
        (if dp.(i - 1).(j) >= dp.(i).(j - 1) then dp.(i - 1).(j) else dp.(i).(j - 1))
    done
  done;
  dp.(n).(m)

La ligne 0 et la colonne 0 valent 0 (PLSC avec une chaîne vide). Diagonale +1 si les caractères coïncident, sinon maximum des deux voisins. Coût $\Theta (nm)$.

let sac objets capacite =
  let n = Array.length objets in
  let dp = Array.make_matrix (n + 1) (capacite + 1) 0 in
  for i = 1 to n do
    let (po, va) = objets.(i - 1) in
    for w = 0 to capacite do
      dp.(i).(w) <- dp.(i - 1).(w);
      if po <= w && dp.(i - 1).(w - po) + va > dp.(i).(w) then
        dp.(i).(w) <- dp.(i - 1).(w - po) + va
    done
  done;
  dp.(n).(capacite)

dp.(i).(w) est la meilleure valeur avec les i premiers objets sous capacité w : on choisit, pour l'objet i, le meilleur entre « sans » et « avec ». Coût $\Theta (nW)$. Le glouton par ratio (chapitre 12) ne donnait pas cet optimum.

let levenshtein a b =
  let n = String.length a and m = String.length b in
  let mini x y = if x <= y then x else y in
  let dp = Array.make_matrix (n + 1) (m + 1) 0 in
  for i = 0 to n do dp.(i).(0) <- i done;     (* i suppressions *)
  for j = 0 to m do dp.(0).(j) <- j done;     (* j insertions *)
  for i = 1 to n do
    for j = 1 to m do
      let c = if a.[i - 1] = b.[j - 1] then 0 else 1 in
      dp.(i).(j) <-
        mini (mini (dp.(i - 1).(j) + 1) (dp.(i).(j - 1) + 1)) (dp.(i - 1).(j - 1) + c)
    done
  done;
  dp.(n).(m)

Les trois opérations correspondent aux trois cases voisines : suppression (i-1,j), insertion (i,j-1), substitution (i-1,j-1, gratuite si les caractères coïncident). levenshtein "chat" "chien" $=3$. Coût $\Theta (nm)$.

let pieces_du_rendu pieces montant =
  let infini = montant + 1 in
  let m = Array.make (montant + 1) infini in
  let choix = Array.make (montant + 1) (-1) in   (* pièce choisie pour la somme s *)
  m.(0) <- 0;
  for s = 1 to montant do
    List.iter (fun p ->
      if p <= s && m.(s - p) + 1 < m.(s) then begin
        m.(s) <- m.(s - p) + 1;
        choix.(s) <- p
      end
    ) pieces
  done;
  if m.(montant) = infini then None
  else
    let rec remonte s = if s = 0 then [] else choix.(s) :: remonte (s - choix.(s)) in
    Some (remonte montant)

On mémorise, pour chaque somme s, la pièce choix.(s) qui a réalisé l'optimum. La reconstruction part de montant et soustrait à chaque étape la pièce choisie, jusqu'à 0. C'est le schéma général : une table annexe des choix permet de retracer la solution.

let plsc_suite a b =
  let n = String.length a and m = String.length b in
  let dp = Array.make_matrix (n + 1) (m + 1) 0 in
  for i = 1 to n do
    for j = 1 to m do
      if a.[i - 1] = b.[j - 1] then dp.(i).(j) <- dp.(i - 1).(j - 1) + 1
      else dp.(i).(j) <-
        (if dp.(i - 1).(j) >= dp.(i).(j - 1) then dp.(i - 1).(j) else dp.(i).(j - 1))
    done
  done;
  let rec remonte i j =
    if i = 0 || j = 0 then []
    else if a.[i - 1] = b.[j - 1] then remonte (i - 1) (j - 1) @ [a.[i - 1]]
    else if dp.(i - 1).(j) >= dp.(i).(j - 1) then remonte (i - 1) j
    else remonte i (j - 1)
  in
  remonte n m

Après avoir rempli la table, on remonte depuis (n, m) : un caractère commun se trouve sur la diagonale (on le garde et l'on remonte en diagonale) ; sinon on suit la direction qui a fourni le maximum. On renvoie une liste de caractères (et non une chaîne — la construire caractère par caractère sort du programme, cf. chapitre 6).