Compter les chemins dans une grille

Application directe du cours · niveau 1 (application) · NSI (terminale), chapitre 7 — La programmation dynamique

Énoncé

Compter les chemins dans une grille.

On se place en haut à gauche d'une grille de $m \times n$ cases. À chaque pas, on ne peut se déplacer que vers la droite ou vers le bas. Combien de chemins distincts mènent à la case en bas à droite ?

Corrigé

Soit $N (i, j)$ le nombre de chemins menant à la case $(i, j)$ . On a $N (i, j) = N (i - 1, j) + N (i, j - 1)$ , avec $N (0, j) = N (i, 0) = 1$ (une seule façon de longer un bord).


def chemins_grille(m, n):
    table = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            table[i][j] = table[i - 1][j] + table[i][j - 1]
    return table[m - 1][n - 1]

La complexité est $O (m \times n)$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.