Montées d'escalier

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

É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.

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.