Longest Increasing Path in a Matrix

DifficileProgrammation dynamique Graphes Tri topologique

+10

Vous recevez matrix, une grille de nombres entiers comportant m lignes et n colonnes, sous forme d’une liste de lignes. Un chemin se déplace d’une cellule à une autre, d’un pas vers le haut, le bas, la gauche ou la droite à la fois (pas de déplacement en diagonale ni de passage d’un bord à l’autre), et chaque pas doit aboutir sur une valeur strictement supérieure. Renvoyez le nombre de cellules du plus long chemin de ce type. Une cellule seule constitue un chemin de 1 cellule.

Fonction

longestIncreasingPath(matrix: integer-2d-array) → integer

matrixinteger-2d-array: la grille de valeurs, sous forme d’une liste de lignes de longueur égale
Renvoieinteger: le nombre de cellules sur le plus long chemin strictement croissant

Contraintes

1 ≤ m, n ≤ 100, où m = matrix.length et n = matrix[i].length
Chaque ligne a la même longueur n.
0 ≤ matrix[i][j] ≤ 2³¹-1

Exemples

Entrée: matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
Sortie: 7
Explication: Le chemin 3, 4, 5, 6, 7, 8, 9 descend dans la colonne de droite, va vers la gauche le long de la rangée du bas, remonte dans la colonne du milieu et va vers la gauche jusqu’au 9 dans le coin : 7 cases. La plus petite valeur donne un moins bon résultat : à partir du 1, les meilleurs chemins sont 1, 2, 7, 8, 9 et 1, 6, 7, 8, 9, avec 5 cases chacun.

+18 tests cachés à la soumission

Pour aller plus loin

Peux-tu également renvoyer les cellules d’un chemin le plus long, et pas seulement sa longueur ?

Solution

Trace une flèche de chaque cellule vers chaque voisine qui contient une valeur plus grande. Les valeurs augmentent le long de chaque flèche, donc aucune chaîne de flèches ne peut revenir à son point de départ : la grille est un graphe orienté acyclique, et le problème consiste à trouver son plus long chemin. Dans un graphe général, cette question est insoluble pour les grandes entrées, mais en l’absence de cycles, le plus long chemin partant d’une cellule ne dépend que de cette cellule ; tu le calcules donc une seule fois par cellule, et le problème entier se réduit à O(m × n). La recherche en profondeur d’abord avec mémoïsation le calcule de haut en bas ; en épluchant la grille à partir de ses sommets, l’algorithme de Kahn inversé le calcule de bas en haut.

Suivez chaque chemin croissant

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Commencez une marche à partir de chaque cellule. Depuis la cellule où vous vous trouvez, essayez chacun des quatre voisins dont la valeur est supérieure, puis continuez de la même manière jusqu’à ce qu’il ne reste plus aucun voisin de valeur supérieure. Comptez les cellules de chaque marche et conservez le plus grand nombre.

La marche n’a pas besoin d’ensemble des cellules visitées. Les valeurs augmentent à chaque étape, donc la marche ne peut jamais revenir sur une cellule : pour y revenir, il faudrait redescendre jusqu’à la valeur de cette cellule. Gardez les marches dans une pile d’entrées (cellule, longueur). Dépiler une entrée termine une marche à cette cellule, et empiler ses voisins de valeur supérieure la prolonge.

La méthode est correcte, mais désespérément lente, car les marches se ramifient. Sur une grille de 100 × 100 où chaque valeur est la somme de sa ligne et de sa colonne, chaque déplacement vers la droite ou vers le bas est une étape ascendante, et les marches partant du seul coin supérieur gauche sont plus de 10^58. Pire encore, la marche depuis une cellule donnée est recalculée chaque fois qu’une autre marche passe par cette cellule, ce qui constitue le gaspillage éliminé par l’approche suivante.

Algorithme

Pour chaque cellule, empilez (cette cellule, 1).
Dépilez une entrée (cellule, longueur) et mettez à jour la réponse avec longueur.
Empilez (voisin, longueur + 1) pour chaque voisin de la grille dont la valeur est strictement supérieure.
Répétez jusqu’à ce que la pile soit vide, puis passez à la cellule de départ suivante.
Renvoyez la plus grande longueur observée.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    answer = 0
    for sr in range(rows):
        for sc in range(cols):
            # Each entry is one path in progress: the cell it ends on and
            # how many cells it has.
            stack = [(sr, sc, 1)]
            while stack:
                r, c, length = stack.pop()
                answer = max(answer, length)
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                        stack.append((nr, nc, length + 1))
    return answer

Recherche en profondeur avec mémoïsation à l’aide de votre propre pile

Intuition

Soit best[cell] le nombre de cellules du plus long chemin croissant qui commence à cette cellule. Le chemin s’arrête soit à cet endroit, soit son étape suivante va vers un voisin plus grand et se poursuit le long du plus long chemin à partir de ce voisin. Ainsi, best[cell] = 1 + max(best[nb]) parmi les voisins plus grands nb, ou vaut 1 s’il n’y en a aucun. On peut réutiliser cette valeur sans risque grâce à la structure acyclique : les cellules qui précèdent cell dans n’importe quel chemin sont toutes plus petites, elles ne peuvent donc jamais apparaître après elle, et la meilleure suite possible à partir de cell est la même, quelle que soit la façon dont on y est arrivé. Calculez chaque valeur de best une seule fois et stockez-la : l’arborescence exponentielle des parcours se réduit à une seule visite par cellule.

Dans le premier exemple, 9 n’a aucun voisin plus grand, donc best vaut 1 à cet endroit. Ensuite, 8 obtient 2, 7 obtient 3, 6 et 2 obtiennent 4, 5 et 1 obtiennent 5, 4 obtient 6, et 3 obtient 7, la réponse. Chaque cellule examine ses 4 voisins, donc le travail est en O(m × n).

Le code naturel est récursif : une fonction qui renvoie best pour une cellule et s’appelle elle-même pour chaque voisin plus grand. La profondeur des appels est égale à la longueur du chemin suivi, et les contraintes autorisent un chemin qui traverse toutes les cellules : des valeurs qui serpentent dans les deux sens sur une grille de 100 × 100 forment un chemin de 10 000 cellules, alors que Python s’arrête par défaut à 1 000 appels imbriqués. Le code ci-dessous exécute lui-même la récursion, de sorte qu’aucun chemin n’est trop long pour lui. Gardez une pile de cellules et, pour chaque cellule, le nombre de directions parmi les quatre que vous avez déjà essayées. Regardez la cellule au sommet : s’il lui reste une direction, essayez-la et empilez le voisin dans cette direction s’il est plus grand et que son traitement n’est pas terminé. Lorsque les quatre directions ont été essayées, tous les voisins plus grands ont été traités : dépilez alors la cellule et définissez sa valeur best. C’est exactement l’ordre qu’un appel récursif suivrait.

La recherche n’a pas besoin de marque « en cours », contrairement à la détection de cycles. Chaque cellule de la pile est plus grande que celle qui se trouve en dessous, donc un voisin plus grand de la cellule au sommet ne peut jamais se trouver plus bas dans la pile.

Algorithme

Initialise best à 0 (pas encore connu) et un compteur de directions à 0 pour chaque cellule.
Pour chaque cellule dont best vaut 0, empilez-la.
Examinez la cellule au sommet. S’il lui reste une direction à explorer, incrémentez son compteur et empilez le voisin dans cette direction s’il se trouve dans la grille, est plus grand et n’est pas terminé.
Si les quatre directions ont été explorées, dépilez la cellule et définissez best à 1 plus la plus grande valeur de best parmi ses voisins plus grands, ou à 1 si elle n’en a aucun.
Renvoie la plus grande valeur de best.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    # best[r][c]: cells on the longest increasing path that starts at (r, c).
    # 0 means not known yet.
    best = [[0] * cols for _ in range(rows)]
    # step[r][c]: how many of the 4 directions the search has tried from (r, c).
    step = [[0] * cols for _ in range(rows)]
    answer = 0
    for sr in range(rows):
        for sc in range(cols):
            if best[sr][sc]:
                continue
            # Our own stack instead of recursion: a path can be thousands of
            # cells long, past Python's limit of 1,000 nested calls.
            stack = [(sr, sc)]
            while stack:
                r, c = stack[-1]
                d = step[r][c]
                if d < 4:
                    step[r][c] = d + 1
                    nr, nc = r + dirs[d][0], c + dirs[d][1]
                    # The stack only climbs, so a larger neighbour is never on it.
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c] and best[nr][nc] == 0:
                        stack.append((nr, nc))
                    continue
                # Every larger neighbour is finished: build on the best of them.
                stack.pop()
                length = 1
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                        length = max(length, best[nr][nc] + 1)
                best[r][c] = length
                answer = max(answer, length)
    return answer

Épluche la grille depuis ses sommets

Intuition

Inverse la programmation dynamique et construis-la à partir des valeurs les plus élevées, comme l’algorithme de Kahn construit un ordre topologique. Appelle sommet une cellule qui n’a aucun voisin plus grand. Un chemin partant d’un sommet ne peut pas avancer : il contient donc 1 cellule. Supprime tous les sommets en même temps : c’est la couche 1. Certaines cellules n’ont alors plus de voisin plus grand, elles deviennent donc les sommets de ce qu’il reste. Supprime-les dans la couche 2, puis continue jusqu’à ce que la grille soit vide. Le nombre de couches est la réponse.

Pourquoi : une cellule se retrouve dans la couche k exactement lorsque le plus long chemin qui commence à cette cellule contient k cellules. Une cellule est supprimée au tour suivant celui où son dernier voisin plus grand est supprimé ; sa couche est donc égale à 1 plus la couche la plus élevée parmi ses voisins plus grands, ce qui correspond à la formule best[cell] = 1 + max(best[nb]) de l’approche précédente. La couche la plus profonde correspond au début d’un plus long chemin.

Dans le premier exemple, le seul sommet est le 9 (ses voisins sont 8 et 2). En le supprimant, on libère le 8 ; la suppression du 8 libère le 7 ; la suppression du 7 libère le 2 et le 6 ; ces deux cellules libèrent le 1 et le 5 ; le 5 libère le 4, et le 4 libère le 3. Cela fait 7 couches, et le chemin 3, 4, 5, 6, 7, 8, 9 monte en passant par une cellule de chaque couche.

Pour trouver rapidement la couche suivante, compte pour chaque cellule le nombre de voisins plus grands qu’elle qui lui restent. La suppression d’une cellule diminue le compte de chacun de ses voisins strictement plus petits, et tout compte qui atteint 0 place ce voisin dans la couche suivante. Chaque cellule est supprimée une fois et chaque paire de voisins est examinée un nombre constant de fois : le travail est donc en O(m × n), sans pile ni récursion.

Algorithme

Pour chaque cellule, comptez les voisins ayant une valeur supérieure.
Placez dans la couche actuelle chaque cellule dont le compte est égal à 0.
Tant que la couche n’est pas vide, ajoutez 1 au nombre de couches. Pour chaque cellule qu’elle contient, diminuez le compte de chaque voisin strictement plus petit et placez dans la couche suivante tout voisin dont le compte atteint 0.
Faites de la couche suivante la couche actuelle et recommencez.
Renvoyez le nombre de couches.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    # higher[r][c]: neighbours of (r, c) with a larger value, not peeled yet.
    higher = [[0] * cols for _ in range(rows)]
    layer = []
    for r in range(rows):
        for c in range(cols):
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                    higher[r][c] += 1
            # A peak: no neighbour is larger, so a path from it has one cell.
            if higher[r][c] == 0:
                layer.append((r, c))
    layers = 0
    while layer:
        layers += 1
        next_layer = []
        for r, c in layer:
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] < matrix[r][c]:
                    higher[nr][nc] -= 1
                    # Its last larger neighbour is peeled: it is a peak now.
                    if higher[nr][nc] == 0:
                        next_layer.append((nr, nc))
        layer = next_layer
    # Each layer is one step further from a peak; the count is the longest path.
    return layers

Pièges et cas limites

Les bogues ici viennent du mot « strictement », de la récursion profonde et d’habitudes héritées d’autres problèmes de grille.

Comparer avec >= au lieu de >. Avec deux 4 voisins, chacun compte comme une étape supérieure à l’autre, les flèches forment une boucle, une recherche par force brute fait des allers-retours sans fin, et une recherche avec mémoïsation lit une longueur encore en cours de calcul.
La récursion sur des chemins très longs. Une recherche récursive s’enfonce d’autant d’appels que le chemin est long, et les contraintes autorisent un chemin qui traverse chaque cellule : des valeurs qui serpentent dans un sens puis dans l’autre sur une grille de 100 × 100 forment un chemin de 10 000 cellules, soit dix fois la limite par défaut de Python, fixée à 1 000 appels imbriqués. De tels chemins nécessitent une recherche itérative avec votre propre pile, ou une limite de récursion augmentée (sys.setrecursionlimit en Python), et une limite très élevée peut tout de même faire déborder la pile interne de l’interpréteur.
Ignorer les cellules déjà visitées, comme le ferait un remplissage par diffusion. Atteindre une cellule dont le calcul est terminé n’est pas une impasse : sa longueur mémorisée est exactement ce dont la cellule actuelle a besoin. Lisez-la, ne l’ignorez pas.
Commencer uniquement par la plus petite valeur. Dans le premier exemple, le 1 donne 5 cellules, mais la réponse, 7, commence au 3. Le plus long chemin peut commencer à n’importe quelle cellule qui n’a aucun voisin plus petit, et il peut y en avoir plusieurs.
Renvoyer 0. Chaque cellule constitue un chemin de 1 cellule ; une grille de valeurs égales, ou une grille de 1 × 1, a donc pour réponse 1. Initialisez la longueur de chaque cellule à 1, et non à 0.
Dans l’approche par élimination, diminuer le compte d’un voisin de valeur égale. Seul un voisin strictement plus petit a perdu un voisin plus grand.

Questions fréquentes4

Quelle est la complexité temporelle du plus long chemin croissant dans une matrice ?

Temps O(m × n) et espace O(m × n) avec une recherche en profondeur d’abord mémoïsée ou avec un épluchage topologique. Chacune des m × n cellules est traitée une fois et examine ses 4 voisines un nombre constant de fois, et chaque méthode conserve un nombre par cellule. Essayer tous les chemins depuis chaque cellule est exponentiel : sur une grille de 100 × 100 où chaque valeur est la somme de sa ligne et de sa colonne, plus de 10^58 chemins partent du coin supérieur gauche.

Pourquoi ce problème ne nécessite-t-il pas d’ensemble des sommets visités ?

Un chemin qui ne fait que monter ne peut jamais revenir à une cellule, car il devrait redescendre jusqu’à la valeur de cette cellule. La règle de stricte croissance interdit donc déjà les revisites, et le graphe des déplacements ne contient aucun cycle. C’est aussi pourquoi la mémoïsation est sûre : les cellules précédant une cellule donnée ne peuvent pas interférer avec le chemin qui suit.

Le plus long chemin croissant dans une matrice relève-t-il de la programmation dynamique ou d’un problème de graphe ?

Les deux. C’est le plus long chemin dans un graphe orienté acyclique, ce qui relève de la programmation dynamique selon un ordre topologique : la réponse pour une cellule est égale à 1 plus la meilleure réponse parmi ses voisins de valeur supérieure. Une recherche en profondeur avec mémoïsation remplit le tableau dans l’ordre où la recherche termine le traitement des cellules, tandis que l’élimination topologique le remplit couche par couche, en commençant par les sommets. Trier les cellules par valeur décroissante donne un troisième ordre valide, au prix d’une complexité de O(m × n × log(m × n)) pour le tri.

En quoi cela diffère-t-il de la plus longue sous-séquence croissante ?

Une sous-séquence peut ignorer des éléments et doit conserver leur ordre, tandis qu’un chemin doit ici avancer vers une cellule adjacente, dans l’une des quatre directions. Le problème de la sous-séquence relève de la programmation dynamique sur une ligne ; celui-ci relève de la programmation dynamique sur une grille transformée en graphe. Tous deux reposent sur le même fait : une chaîne strictement croissante ne peut jamais revenir sur elle-même.

Python

def longestIncreasingPath(matrix):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]

Attendu

Longest Increasing Path in a Matrix

Fonction

Contraintes

Exemples

Indices

Solution

Suivez chaque chemin croissant

Recherche en profondeur avec mémoïsation à l’aide de votre propre pile

Épluche la grille depuis ses sommets

Pièges et cas limites

Questions fréquentes4

Problèmes similaires