Pascal's Triangle

Q: Quelle est la complexité temporelle de la génération du triangle de Pascal ?

Construire chaque ligne à partir de celle du dessus prend un temps de O(n²) pour n lignes, car le triangle comporte environ n²/2 entrées et chacune nécessite une seule addition. C’est optimal, puisque tu dois écrire chaque entrée du résultat. En dehors du résultat, cette méthode utilise un espace supplémentaire de O(1) .

Q: Quel est le lien entre le triangle de Pascal et les coefficients binomiaux ?

L’entrée k de la ligne r , en comptant les deux à partir de 0, est le coefficient binomial C(r, k) , le nombre de façons de choisir k éléments parmi r . La règle selon laquelle chaque entrée est la somme des deux entrées au-dessus d’elle est l’identité C(r, k) = C(r-1, k-1) + C(r-1, k) . C’est aussi pourquoi la somme des éléments de la ligne r est égale à 2^r .

Q: Peux-tu calculer une ligne sans construire les lignes qui la précèdent ?

Oui. Commencez par 1 et obtenez chaque entrée suivante à partir de la précédente : C(r, k) = C(r, k-1) × (r-k+1) / k . Multipliez avant de diviser afin que la division soit exacte, et utilisez un entier de 64 bits pour le produit. La ligne r prend alors un temps O(r) et aucune autre ligne.

Q: Pourquoi le triangle de Pascal est-il un problème de programmation dynamique ?

Chaque entrée dépend de deux sous-problèmes plus petits, les entrées au-dessus d’elle, et ces sous-problèmes se chevauchent fortement : la récursion simple les recalcule encore et encore. Construire les lignes dans l’ordre permet de stocker chaque sous-problème une seule fois et de le réutiliser, ce qui transforme un travail exponentiel en O(n²) .

FacileProgrammation dynamique

+10

Dans le triangle de Pascal, la première ligne est [1]. Chaque ligne suivante comporte une entrée de plus, commence et se termine par 1, et chaque entrée intermédiaire est la somme des deux entrées situées juste au-dessus. Tu reçois un entier numRows. Renvoie les numRows premières lignes du triangle, en commençant par la ligne du haut, chaque ligne étant un tableau d’entiers.

Fonction

generate(numRows: integer) → integer-2d-array

numRowsinteger: combien de lignes du triangle construire
Renvoieinteger-2d-array: les numRows premières lignes, en commençant par la ligne du haut

Contraintes

1 ≤ numRows ≤ 30
Chaque valeur des 30 premières lignes tient dans un entier signé de 32 bits. La plus grande est 77558760, au milieu de la ligne 30.

Exemples

Entrée: numRows = 5
Sortie: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Explication: Chaque entrée intérieure additionne les deux entrées situées au-dessus. Dans la quatrième ligne, 3 = 1 + 2 et 3 = 2 + 1. Dans la cinquième ligne, 4 = 1 + 3, 6 = 3 + 3 et 4 = 3 + 1.

Entrée: numRows = 1
Sortie: [[1]]
Explication: Avec une seule ligne, le triangle se réduit à son sommet, [1].

+13 tests cachés à la soumission

Pour aller plus loin

Peux-tu construire uniquement la dernière ligne dans un seul tableau, en la mettant à jour sur place ligne après ligne au lieu de conserver les lignes précédentes ? Dans quel sens la boucle interne doit-elle s’exécuter, et pourquoi ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La règle qui définit le triangle est récursive : une entrée est la somme de deux entrées de la ligne supérieure. Appliquer cette règle depuis le début pour chaque entrée recalcule sans cesse les mêmes valeurs, et le travail double à chaque ligne. Les lignes que tu dois renvoyer sont exactement les réponses mémorisées à ces problèmes plus petits ; construis donc le triangle de haut en bas et lis chaque ligne à partir de celle que tu as construite juste avant.

Calculez chaque entrée de manière récursive

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Numérotez les lignes et les positions à l’intérieur d’une ligne à partir de 0. La définition du triangle devient une fonction : entry(row, col) vaut 1 lorsque col vaut 0 ou est égal à row, c’est-à-dire sur les deux bords, et sinon vaut entry(row-1, col-1) + entry(row-1, col). Appelez-la pour chaque position de chaque ligne et vous obtenez le triangle. C’est correct parce que c’est la définition, mot pour mot.

Le problème, c’est le nombre d’appels qu’elle effectue. La récursion ne s’arrête qu’aux bords, où elle renvoie 1, donc le calcul d’une entrée de valeur v nécessite environ 2v appels. La ligne r atteint 2^r, donc les 30 lignes nécessitent au total environ 2^31 appels, soit plus de deux milliards. Les mêmes petites entrées sont recalculées des millions de fois : entry(2, 1) intervient dans le calcul de presque toutes les valeurs en dessous.

Algorithme

Écrivez entry(row, col) : renvoyez 1 si col vaut 0 ou si col est égal à row.
Sinon, renvoyez entry(row-1, col-1) + entry(row-1, col).
Pour chaque row de 0 à numRows-1, recueillez entry(row, col) pour chaque col de 0 à row.
Renvoyez la liste des lignes.

def pascalEntry(row, col):
    if col == 0 or col == row:
        return 1  # the edges of the triangle
    return pascalEntry(row - 1, col - 1) + pascalEntry(row - 1, col)


def generate(numRows):
    triangle = []
    for row in range(numRows):
        triangle.append([pascalEntry(row, col) for col in range(row + 1)])
    return triangle

Construisez chaque ligne à partir de la ligne au-dessus

Intuition

La version récursive continue de demander les valeurs des lignes précédentes, et tu construis déjà ces lignes de toute façon. Calcule donc les lignes dans l’ordre, de haut en bas, et lorsque tu remplis la ligne r, lis les valeurs dont tu as besoin directement dans la ligne r-1, qui est déjà calculée. Chaque entrée ne nécessite alors qu’une addition. C’est la programmation dynamique sous sa forme la plus simple : le tableau des réponses intermédiaires est lui-même le résultat.

Commence la ligne r avec r + 1 uns, ce qui définit les deux bords. Ensuite, pour chaque position intérieure c de 1 à r-1, définis sa valeur comme above[c-1] + above[c]. Les lignes 0 et 1 n’ont pas de positions intérieures, elles restent donc [1] et [1, 1] sans cas particulier.

Le triangle contient 1 + 2 + ... + n, soit environ n²/2 entrées, et chacune demande un temps constant : le travail est donc de O(n²). À part le résultat, que tu dois de toute façon renvoyer, la méthode ne nécessite pas de mémoire supplémentaire. Pour numRows = 30, cela représente 465 entrées au lieu de deux milliards d’appels.

Algorithme

Commence par une liste de lignes vide.
Pour chaque row de 0 à numRows-1, crée row + 1 uns.
Pour chaque col de 1 à row-1, définis sa valeur comme la somme des positions col-1 et col de la ligne précédente.
Ajoute la ligne et continue. Renvoie la liste.

def generate(numRows):
    triangle = [[1]]
    for row in range(1, numRows):
        above = triangle[-1]
        values = [1] * (row + 1)  # both edges are 1
        for col in range(1, row):
            values[col] = above[col - 1] + above[col]
        triangle.append(values)
    return triangle

Pièges et cas limites

Les boucles sont courtes, donc les erreurs concernent les limites et les premières lignes.

Renvoyer numRows + 1 lignes. Si tu numérote les lignes à partir de 0, la dernière dont tu as besoin est la ligne numRows-1.
Exécuter la boucle interne sur les bords. La position 0 n'a pas de parent à gauche et la position row n'a pas de parent à droite, donc lire above[col-1] ou above[col] à ces endroits dépasse les limites. Remplis uniquement les positions 1 à row-1.
Écrire une plage qui échoue pour les petites lignes. 1..<row en Swift provoque un plantage lorsque row vaut 0, et 2:(row-1) en R compte à rebours jusqu'à 1 lorsque row vaut 2. Protège-les, ou initialise les positions internes à des tableaux contenant un élément afin que les lignes 0 et 1 ne nécessitent aucune boucle.
Calculer les entrées avec des factorielles. C(29, 14) tient dans un int, mais 29! déborde même un entier 64 bits : une formule basée sur des factorielles affiche donc des nombres erronés dans les lignes du bas.
Réutiliser un même tableau pour chaque ligne. Si tu ajoutes le même tableau à chaque fois, puis que tu le modifies, toutes les lignes de la réponse finissent par être identiques à la dernière.

Questions fréquentes4

Quelle est la complexité temporelle de la génération du triangle de Pascal ?

Construire chaque ligne à partir de celle du dessus prend un temps de O(n²) pour n lignes, car le triangle comporte environ n²/2 entrées et chacune nécessite une seule addition. C’est optimal, puisque tu dois écrire chaque entrée du résultat. En dehors du résultat, cette méthode utilise un espace supplémentaire de O(1).

Quel est le lien entre le triangle de Pascal et les coefficients binomiaux ?

L’entrée k de la ligne r, en comptant les deux à partir de 0, est le coefficient binomial C(r, k), le nombre de façons de choisir k éléments parmi r. La règle selon laquelle chaque entrée est la somme des deux entrées au-dessus d’elle est l’identité C(r, k) = C(r-1, k-1) + C(r-1, k). C’est aussi pourquoi la somme des éléments de la ligne r est égale à 2^r.

Peux-tu calculer une ligne sans construire les lignes qui la précèdent ?

Oui. Commencez par 1 et obtenez chaque entrée suivante à partir de la précédente : C(r, k) = C(r, k-1) × (r-k+1) / k. Multipliez avant de diviser afin que la division soit exacte, et utilisez un entier de 64 bits pour le produit. La ligne r prend alors un temps O(r) et aucune autre ligne.

Pourquoi le triangle de Pascal est-il un problème de programmation dynamique ?

Chaque entrée dépend de deux sous-problèmes plus petits, les entrées au-dessus d’elle, et ces sous-problèmes se chevauchent fortement : la récursion simple les recalcule encore et encore. Construire les lignes dans l’ordre permet de stocker chaque sous-problème une seule fois et de le réutiliser, ce qui transforme un travail exponentiel en O(n²).

Python

def generate(numRows):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Entrée

numRows = 5

Attendu

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]