Entraînez-vous pour la Piscine de l'École 42

Il est toujours bon de commencer par quelques cas de test. Commençons par de petits cas et voyons si nous pouvons trouver une sorte de modèle.

• N = 1: [1]
• N = 2: [1, 1], [2]
• N = 3: [1, 2], [1, 1, 1], [2, 1]
• N = 4: [1, 1, 2], [2, 2], [1, 2, 1], [1, 1, 1, 1], [2, 1, 1]

Quelle est la relation ?

Le seul moyen d'arriver à N = 3, est d'abord d'arriver à N = 1, puis de monter de 2 pas, ou d'arriver à N = 2 et de monter d'un pas. Donc f(3) = f(2) + f(1).

Cela vaut-il pour N = 4 ? Oui. Puisque nous ne pouvons arriver à la 4ème étape qu'en allant à la 3ème étape et en remontant d'une unité, ou en allant à la 2ème étape et en remontant de deux. Donc f(4) = f(3) + f(2).

Pour généraliser, f (n) = f (n - 1) + f (n - 2). C'est simplement la Suite de Fibonacci !

def staircase(n):
  if n <= 1:
    return 1
  return staircase(n - 1) + staircase(n - 2)

Bien sûr, c'est vraiment lent (O(2N)) - nous faisons beaucoup de calculs répétés ! Nous pouvons le faire beaucoup plus rapidement en calculant simplement de manière itérative :

def staircase(n):
  a, b = 1, 2
  for _ in range(n - 1):
    a, b = b, a + b
  return a

Maintenant, essayons de généraliser ce que nous avons appris pour que cela fonctionne si vous pouvez faire un certain nombre d'étapes à partir de l'ensemble X. Un raisonnement similaire nous dit que si X = {1, 3, 5}, alors notre algorithme devrait être f(n) = f(n - 1) + f(n - 3) + f(n - 5). Si n < 0, alors nous devrions retourner 0 car nous ne pouvons pas partir d'un nombre de pas négatif.

def staircase(n, X):
  if n < 0:
    return 0
  elif n == 0:
    return 1
  else:
    return sum(staircase(n - x, X) for x in X)

C'est encore une fois très lent (O(|X|N)) puisque nous répétons à nouveau les calculs. Nous pouvons utiliser la programmation dynamique pour l'accélérer.

Chaque cache d'entrée [i] contiendra le nombre de façons dont nous pouvons arriver à l'étape i avec l'ensemble X. Ensuite, nous allons construire le tableau à partir de zéro en utilisant la même récurrence que précédemment :

def staircase(n, X):
  cache = [0 for _ in range(n + 1)]
  cache[0] = 1
  for i in range(1, n + 1):
    cache[i] += sum(cache[i - x] for x in X if i - x >= 0)
  return cache[n]

Cela prend maintenant le temps O(N * |X|) et l'espace O(N).