OCaml (option informatique) · Chapitre 13 · Exercice de TD

Montées d'escalier

Programmation dynamique · niveau 2

Énoncé

On monte un escalier de n marches par pas de $1$ ou $2$ . Écrire escalier n comptant le nombre de façons.

Corrigé

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.

Exercices semblables

Chemin de coût minimal dans une grille corrigé
Plus longue sous-suite commune corrigé
Sac à dos 0/1 corrigé
Distance d'édition corrigé
Reconstruire les pièces du rendu corrigé

Le cours du chapitre · Tous les exercices du chapitre