Chemins uniques et somme minimale des chemins sur des grilles

Chemins uniques (LeetCode 62) pose la question suivante : dans une grille m×n, combien de chemins distincts vont du coin supérieur gauche au coin inférieur droit si vous pouvez uniquement vous déplacer vers la droite ou vers le bas ? Pour une grille 3×7, la réponse est 28. L’idée essentielle est que tout chemin vers la cellule (i,j) doit provenir soit de (i-1,j) (au-dessus), soit de (i,j-1) (à gauche), ce qui conduit naturellement à une formulation DP 2D.

Définissez dp[i][j] comme le nombre de chemins vers la cellule (i,j). La première ligne et la première colonne ne contiennent que des 1 (il n’existe qu’une seule façon d’atteindre chaque cellule de la ligne supérieure ou de la colonne la plus à gauche). Pour les autres cellules : dp[i][j] = dp[i-1][j] + dp[i][j-1]. Remplissez le tableau ligne par ligne ; la réponse est dp[m-1][n-1]. Complexité temporelle : O(m×n) ; espace : O(m×n), réductible à O(n).

Puisque dp[i][j] dépend uniquement de la ligne actuelle et de la ligne précédente, vous pouvez remplacer le tableau 2D complet par un seul tableau 1D. Initialisez toutes les valeurs à 1, puis mettez-les à jour sur place pour chaque ligne : dp[j] += dp[j-1]. Après le traitement de la ligne i, dp[j] contient la valeur qui était celle de dp[i][j] dans le tableau 2D. Il s’agit d’un schéma d’optimisation courant pour les problèmes de DP 2D.

Chemins uniques II (LeetCode 63) ajoute des obstacles (cellules marquées par 1) à la grille. Tout chemin traversant un obstacle est invalide ; dp[i][j] = 0 si obstacle[i][j] == 1. Sinon, la récurrence reste la même : dp[i][j] = dp[i-1][j] + dp[i][j-1]. Si le départ ou l’arrivée est bloqué, la réponse est immédiatement 0. Initialisez soigneusement les cas de base : dès qu’un 1 apparaît dans la première ligne ou la première colonne, toutes les cellules suivantes de cette ligne ou colonne valent 0.

Somme minimale d’un chemin (LeetCode 64) demande, dans une grille m×n remplie d’entiers non négatifs, de trouver le chemin du coin supérieur gauche au coin inférieur droit qui minimise la somme de tous les nombres rencontrés (en se déplaçant uniquement vers la droite ou vers le bas). Par exemple, dans [[1,3,1],[1,5,1],[4,2,1]], le chemin 1→3→1→1→1 donne une somme de 7. L’état DP est le même que pour les chemins uniques, mais la récurrence utilise désormais le minimum au lieu de l’addition.

Définissez dp[i][j] comme le coût minimal pour atteindre la cellule (i,j). Cas de base : dp[0][0] = grid[0][0]. Première ligne : dp[0][j] = dp[0][j-1] + grid[0][j] (le seul chemin vient de la gauche). Première colonne : dp[i][0] = dp[i-1][0] + grid[i][0] (le seul chemin vient du dessus). Cas général : dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Il s’agit d’une traduction directe du principe d’optimalité.

Si vous êtes autorisé à modifier la grille d’entrée, vous pouvez la mettre à jour sur place afin d’éviter d’allouer un tableau DP séparé. Cela réduit l’espace auxiliaire à O(1) (en plus de l’entrée). Les examinateurs demandent parfois cette optimisation en entretien : vérifiez d’abord si la modification de l’entrée est autorisée. Dans le cas contraire, l’astuce du tableau glissant 1D offre un espace O(n) sans modifier l’entrée.

Triangle (LeetCode 120) demande la somme minimale d’un chemin du sommet au bas d’un tableau triangulaire, chaque étape menant à un nombre adjacent de la ligne suivante. La DP ascendante est la plus simple : commencez à l’avant-dernière ligne et, pour chaque cellule, ajoutez le minimum des deux cellules qui se trouvent directement en dessous. Cela évite de suivre les indices de départ et fait naturellement remonter la réponse jusqu’au sommet.

Jeu du donjon (LeetCode 174) demande la santé initiale minimale nécessaire pour sauver une princesse dans le coin inférieur droit d’une grille contenant des cellules négatives (dégâts) et positives (soins). Vous devez vous déplacer vers la droite ou vers le bas. L’astuce consiste à remplir le tableau DP à rebours (du coin inférieur droit vers le coin supérieur gauche) en calculant la santé minimale nécessaire dans chaque cellule. Pour chaque cellule : dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). La santé doit toujours rester au moins égale à 1.

Les problèmes de DP sur grille partagent la même structure, mais diffèrent par le sens de remplissage et l’opération de transition : les chemins uniques utilisent l’addition (compter toutes les possibilités), la somme minimale d’un chemin utilise le minimum (optimiser), et le jeu du donjon se remplit à rebours (santé nécessaire en fonction de la suite du chemin). Face à une nouvelle DP sur grille, posez-vous les questions suivantes : (1) que représente chaque cellule ? (2) dans quel sens dois-je remplir la grille ? (3) quelle opération combine les cellules voisines ? Les réponses à ces trois questions révèlent la solution complète.

Tous les problèmes de DP sur grille présentés ici s’exécutent en temps O(m×n). L’espace varie de O(m×n) pour un tableau complet à O(n) avec un tableau glissant 1D, et à O(1) d’espace auxiliaire lorsque la grille peut être modifiée sur place. En entretien, présentez l’optimisation de l’espace en O(n) après la solution en O(m×n) : cela montre que vous connaissez les compromis. Pour tous les problèmes, vérifiez également s’il existe une solution gloutonne plus directe (comme la formule mathématique des chemins uniques).

Vérifiez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation — abordés dans cette leçon.

Dans cette leçon, vous avez appris que : les chemins uniques remplissent un tableau 2D avec dp[i][j] = dp[i-1][j] + dp[i][j-1] et peuvent être calculés en O(1) grâce à la combinatoire ; la somme minimale d’un chemin utilise la même structure, mais remplace l’addition par min pour obtenir le coût optimal du chemin ; et tous les problèmes de DP sur grille suivent le schéma consistant à définir un état par cellule et à choisir un opérateur de transition (somme, min, max). Nous allons maintenant étudier la sous-séquence commune la plus longue à l’aide de la DP 2D appliquée à deux séquences.