Climbing Stairs
Tu te trouves en bas d’un escalier de n marches. À chaque déplacement, tu montes soit 1 marche, soit 2 marches. Deux montées comptent comme différentes si leurs séquences de déplacements diffèrent, donc 1, 2 et 2, 1 sont deux façons différentes. Ta fonction reçoit n et renvoie le nombre de façons distinctes d’atteindre le sommet.
Fonction
- ninteger
- le nombre de marches de l’escalier
- Renvoieinteger
- le nombre de séquences distinctes de pas de 1 et de pas de 2 qui permettent d’atteindre la marche n
Contraintes
1 ≤ n ≤ 45- La réponse tient dans un entier signé de 32 bits :
n = 45donne1836311903.
Exemples
- Entrée
- n = 3
- Sortie
- 3
- Explication
- Trois marches peuvent être gravies de
1, 1, 1, de1, 2ou de2, 1, il y a donc 3 façons.
- Entrée
- n = 5
- Sortie
- 8
- Explication
- Chaque montée vers l’étape 5 se termine par un saut d’une étape depuis l’étape 4 (5 façons d’y arriver) ou par un saut de deux étapes depuis l’étape 3 (3 façons), donc la réponse est
5 + 3 = 8.
+13 tests cachés à la soumission
Pour aller plus loin
Que se passe-t-il si certaines marches sont cassées et que vous ne pouvez jamais vous tenir dessus ? Comment la relation de récurrence change-t-elle, et quel est le décompte pour une marche cassée ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Regardez le dernier déplacement de n’importe quelle montée jusqu’à l’étape
n. Où auriez-vous pu vous trouver juste avant ?Chaque montée jusqu’à la marche
nse termine par un pas d’une marche depuis la marchen-1ou par un pas de deux marches depuis la marchen-2, jamais les deux. Le nombre de façons d’atteindrenest donc égal au nombre de façons d’atteindren-1plus le nombre de façons d’atteindren-2.Commencez avec le nombre de façons pour 1 marche (1 façon) et 2 marches (2 façons), puis progressez. Vous n’avez besoin que des deux derniers nombres, et chaque nouveau nombre est leur somme.
Solution
Énumérer toutes les montées ne fonctionne pas : un escalier de 45 marches en compte 1836311903. L’astuce consiste à examiner le dernier pas. Toute montée jusqu’à la marche n passe par la marche n-1 ou la marche n-2 juste avant la fin, ce qui donne ways(n) = ways(n-1) + ways(n-2), la récurrence de Fibonacci. Calculez-la de bas en haut et deux variables suffisent.
Récursion simple sur le dernier coup
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Répartis les montées jusqu’à la marche n selon leur dernier mouvement. Une montée qui se termine par un pas de 1 se trouvait à la marche n-1 juste avant, et il existe ways(n-1) montées de ce type. Une montée qui se termine par un pas de 2 se trouvait à la marche n-2, et il en existe ways(n-2). Chaque montée se termine d’une manière ou de l’autre, jamais des deux à la fois, donc ways(n) = ways(n-1) + ways(n-2).
La récursion nécessite deux cas de base. Il y a une montée pour une marche et deux montées pour deux marches (1, 1 et 2). Dans les deux cas, la réponse est égale à n : la fonction renvoie donc n lorsque n ≤ 2, et la somme sinon.
La réponse est correcte, mais le travail explose. climbStairs(5) demande deux fois la marche 3 et trois fois la marche 2, soit 9 appels au total, et le nombre d’appels augmente comme les réponses elles-mêmes. Pour n = 45, la fonction effectue 2269806339 appels, soit environ 2.3 × 10^9, beaucoup trop pour respecter une limite de temps. La récursion n’a que n niveaux de profondeur, donc la pile utilise un espace de O(n).
Algorithme
- Si
n ≤ 2, renvoien. - Compte les montées qui atteignent la marche
n-1avec un appel récursif. - Compte les montées qui atteignent la marche
n-2avec un deuxième appel récursif. - Renvoie la somme des deux nombres.
def climbStairs(n):
if n <= 2:
return n # 1 step: one way, 2 steps: two ways
return climbStairs(n - 1) + climbStairs(n - 2)La récursivité avec une mémoïsation
Intuition
La récursion est lente uniquement parce qu’elle oublie. Chaque décompte dépend uniquement de k, donc dès que tu connais le décompte pour l’étape k, il ne change jamais. Garde un mémo, un tableau avec une case par étape, et écris-y chaque décompte la première fois que tu le calcules. Toute demande ultérieure pour la même étape lit la case au lieu de lancer à nouveau la récursion.
Maintenant, chacun des décomptes de l’étape 3 à l’étape n est calculé une seule fois, avec une addition. Pour n = 5, les appels descendent jusqu’à l’étape 2 une seule fois, puis les réponses remontent sous la forme de 3, 5 et 8, et la deuxième demande pour l’étape 3 est une consultation. Cela prend un temps de O(n) au lieu de milliards d’appels.
Le mémo contient n + 1 nombres et la récursion a toujours une profondeur de n niveaux, donc l’espace est de O(n). Un 0 dans une case signifie que la valeur n’est pas encore connue, ce qui est sans risque puisque chaque décompte réel est d’au moins 1.
Algorithme
- Crée un mémo de
n + 1cases, toutes à 0. - Dans la fonction auxiliaire récursive, retourne
klorsquek ≤ 2. - Si la case du mémo pour
kvaut 0, remplis-la avec la somme des résultats de la fonction auxiliaire pourk-1etk-2. - Retourne la case du mémo.
- Appelle la fonction auxiliaire sur
n.
def climbStairs(n):
memo = [0] * (n + 1) # memo[k] = ways to reach step k, 0 = not known yet
def ways(k):
if k <= 2:
return k
if memo[k] == 0:
memo[k] = ways(k - 1) + ways(k - 2)
return memo[k]
return ways(n)De bas en haut avec deux variables
Intuition
Inverse la récursion. Au lieu de commencer par le haut et de descendre, commence par le bas et remonte. Lorsque tu calcules le nombre pour l’étape k, les nombres pour k-1 et k-2 sont déjà connus, et aucune valeur plus ancienne n’est jamais relue. Deux variables remplacent donc toute la mémorisation.
Fais en sorte que prev contienne le nombre pour l’étape k-2 et que curr contienne celui de l’étape k-1. Commence avec prev = 1 et curr = 2, les nombres pour les étapes 1 et 2. À chaque étape, additionne-les dans next, puis fais avancer la paire. Pour n = 5, la paire passe de (1, 2) à (2, 3), puis à (3, 5) et (5, 8), et curr = 8 est la réponse.
La boucle s’exécute n-2 fois, avec une addition à chaque fois : le temps d’exécution est O(n) et elle conserve trois entiers, soit un espace de O(1). Calcule next avant d’écraser prev, sinon la somme utilise la mauvaise valeur.
Algorithme
- Si
n ≤ 2, renvoien. - Définis
prev = 1etcurr = 2. - Pour
kde 3 àn, calculenext = prev + curr, puis définisprev = curretcurr = next. - Renvoie
curr.
def climbStairs(n):
if n <= 2:
return n
prev, curr = 1, 2 # ways to reach steps 1 and 2
for _ in range(n - 2):
prev, curr = curr, prev + curr
return curr
Pièges et cas limites
La récurrence est courte, donc la plupart des bogues se trouvent dans les cas de base, le temps d’exécution et la limite des 32 bits.
- Soumettre la récursion directe. Elle réussit les petits tests, puis nécessite environ
2.3 × 10^9appels pourn = 45. Stocke chaque compte une seule fois. - Cas de base incorrects. Pour deux marches, il y a deux montées :
1, 1et2. Renvoyer 1 pourn = 2décale toutes les réponses suivantes : tu obtiendrais 2 pourn = 3au lieu de 3. - Compter les choix au lieu des séquences.
1, 2et2, 1sont deux montées. Compter uniquement le nombre de pas de 2 que tu fais donnen/2 + 1, soit 3 pourn = 5au lieu de 8. - Remplir un tableau sans garde-fou. Avec
n = 1, un tableau den + 1 = 2emplacements n’a pas de place pour le compte de la marche 2. Renvoienimmédiatement lorsquen ≤ 2. - Exécuter une étape de trop. Le compte pour 45 marches, 1836311903, tient sur 32 bits, mais celui pour 46 marches est 2971215073 et ne tient pas. Une boucle qui calcule une valeur supplémentaire déborde et produit un nombre négatif en Java, C ou C#.
Questions fréquentes4
Pourquoi le problème des escaliers est-il un problème de Fibonacci ?
Chaque montée jusqu’à la marche n se termine par un pas de 1 marche depuis n-1 ou par un pas de 2 marches depuis n-2, donc ways(n) = ways(n-1) + ways(n-2). C’est la règle de Fibonacci. Avec ways(1) = 1 et ways(2) = 2, les nombres de possibilités sont 1, 2, 3, 5, 8, 13, ce qui correspond à la suite de Fibonacci décalée d’un rang : ways(n) = F(n+1).
Quelle est la complexité temporelle de Climbing Stairs ?
La boucle ascendante effectue n-2 additions ; elle s’exécute donc en temps O(n) avec un espace supplémentaire O(1). La récursion simple a une complexité exponentielle : son nombre d’appels augmente d’un facteur d’environ 1.618 à chaque étape et atteint 2269806339, soit environ 2.3 × 10^9, pour n = 45. La mémoïsation ramène la récursion à un temps O(n) et à un espace O(n).
Quelle est la différence entre la mémorisation et la solution ascendante ?
La mémoïsation conserve la fonction récursive et met en cache chaque résultat la première fois qu’il est calculé : elle fonctionne donc de haut en bas et nécessite la pile d’appels et une table. La boucle ascendante calcule les nombres dans l’ordre croissant, de sorte que chaque valeur dont elle a besoin est déjà connue et qu’aucune récursion n’intervient. Les deux effectuent un travail en O(n). La boucle permet également de se passer de la table et de ne conserver que deux nombres.
Comment résoudre le problème des escaliers avec des pas de 1, 2 ou 3 ?
Répartissez à nouveau les montées selon leur dernier mouvement : ways(n) = ways(n-1) + ways(n-2) + ways(n-3). Commencez par ways(0) = 1 (la montée vide), ways(1) = 1 et ways(2) = 2, et conservez les trois derniers décomptes plutôt que deux. Le temps reste en O(n) et l’espace en O(1).
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
Python
def climbStairs(n):
# Écrivez le code iciCas 1
Cas 2
Entrée
n = 3
Attendu
3