Préparez 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).