Prépa Code Connexion Inscription

On considere un escalier de n marches. A chaque pas, on peut monter 1 marche ou 2 marches. Ecrire une fonction nb_facons_escalier(n) qui renvoie le nombre de facons differentes d'atteindre la marche n en partant du bas (marche 0).

Par exemple, pour n = 3, les facons sont : - 1 + 1 + 1 - 1 + 2 - 2 + 1

Soit 3 facons.

On utilisera une approche par programmation dynamique. Si f(n) est le nombre de facons d'atteindre la marche n : - f(0) = 1 (une seule facon de rester en bas) - f(1) = 1 - f(n) = f(n-1) + f(n-2) pour n >= 2