Unique Paths

Pense au dernier déplacement du robot vers la case en bas à droite. Il est soit descendu depuis la case au-dessus, soit venu de droite depuis la case à gauche, jamais les deux. Les chemins dans une grille de m × n sont donc les chemins dans la grille raccourcie d’une ligne, uniquePaths(m-1, n), plus les chemins dans la grille moins large d’une colonne, uniquePaths(m, n-1).

La récursion s’arrête lorsqu’il ne reste qu’une ligne ou une colonne dans la grille : le robot ne peut alors qu’avancer tout droit, il existe donc exactement 1 chemin. Chaque chemin se termine par l’un des deux déplacements, donc chaque chemin est compté une fois et le total est correct.

Cette méthode est lente, car chaque chemin se termine par un cas de base qui renvoie 1 : le nombre d’appels est donc au moins égal à la réponse elle-même. Une grille de 17 × 17 nécessite plus de 600 millions d’appels, et les tests vont jusqu’à des réponses proches de 1.6 × 10^9. Les mêmes grilles plus petites sont calculées de nombreuses fois : (m-1, n-1) est atteint une fois depuis chacun de ses deux parents, et les répétitions se multiplient à mesure que l’on descend.

La récursion interroge les mêmes cellules encore et encore, alors qu’il n’y a que m × n cellules. Compte une seule fois les chemins vers chaque cellule, dans un ordre où les cellules dont tu as besoin sont toujours prêtes.

État : paths[r][c] est le nombre de chemins allant de la cellule en haut à gauche jusqu’à la ligne r, colonne c. Récurrence : paths[r][c] = paths[r-1][c] + paths[r][c-1], les chemins qui arrivent d’en haut plus ceux qui arrivent de la gauche. Cas de base : chaque cellule de la première ligne et de la première colonne a 1 chemin, en ligne droite. Ordre : ligne par ligne, de gauche à droite, afin que la cellule au-dessus et celle à gauche soient remplies avant que tu en aies besoin.

Pour m = 3 et n = 4, les lignes sont 1 1 1 1, puis 1 2 3 4, puis 1 3 6 10, et la réponse est la dernière cellule, 10.

Regarde maintenant ce que lit le remplissage : seulement la ligne au-dessus et la ligne que tu remplis. Garde donc une seule ligne. Avant de mettre à jour row[c], elle contient encore le compte de la ligne au-dessus, et row[c-1] contient déjà le nouveau compte à sa gauche ; ainsi, row[c] += row[c-1] correspond à toute la récurrence. La complexité temporelle reste O(m × n), et la mémoire passe de O(m × n) à O(n).

Chaque chemin comporte exactement m-1 déplacements vers le bas et n-1 déplacements vers la droite, soit m+n-2 déplacements au total, dans un certain ordre. Chaque ordre correspond à un chemin valide : le robot ne fait jamais plus de m-1 déplacements vers le bas ni de n-1 déplacements vers la droite, donc il ne sort jamais de la grille. Un chemin revient donc à choisir lesquels des m+n-2 déplacements sont les m-1 déplacements vers le bas, et la réponse est le coefficient binomial C(m+n-2, m-1).

Le tableau de l’approche précédente est le triangle de Pascal tourné sur le côté, ce qui explique pourquoi les deux résultats concordent. Pour calculer le coefficient sans factorielle énorme, construis-le facteur par facteur. Avec N = m+n-2 et k = min(m, n)-1, multiplie par N-k+i, puis divise par i, pour i allant de 1 à k. Après l’étape i, la valeur intermédiaire est C(N-k+i, i), un entier, donc chaque division est exacte.

Pour m = 3 et n = 4 : N = 5, k = 2, et la valeur évolue ainsi : 1 × 4 / 1 = 4, puis 4 × 5 / 2 = 10. En choisissant le côté le plus court, la boucle comporte au plus 99 étapes. Le produit avant la dernière division est égal à k fois la réponse. Pour une grille de 17 × 17, cela donne 16 × 601,080,390, soit environ 9.6 × 10^9, ce qui dépasse la plage d’un entier signé sur 32 bits ; utilise donc un entier sur 64 bits.