Longest Increasing Path in a Matrix

DifficileProgrammazione dinamica Grafi Ordinamento topologico

+10

Ricevi matrix, una griglia di numeri interi con m righe e n colonne, sotto forma di elenco di righe. Un percorso si sposta da una cella a un'altra, di un passo alla volta in alto, in basso, a sinistra o a destra (senza passi diagonali e senza oltrepassare i bordi), e ogni passo deve terminare su un valore strettamente maggiore. Restituisci il numero di celle del percorso più lungo di questo tipo. Una singola cella, da sola, costituisce un percorso di 1 cella.

Funzione

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

matrixinteger-2d-array: la griglia di valori, come un elenco di righe di uguale lunghezza
Restituisceinteger: il numero di celle nel percorso strettamente crescente più lungo

Vincoli

1 ≤ m, n ≤ 100, dove m = matrix.length e n = matrix[i].length
Ogni riga ha la stessa lunghezza n.
0 ≤ matrix[i][j] ≤ 2³¹-1

Esempi

Input: matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
Output: 7
Spiegazione: Il percorso 3, 4, 5, 6, 7, 8, 9 scende lungo la colonna di destra, procede verso sinistra lungo la riga inferiore, risale lungo la colonna centrale e va a sinistra fino al 9 nell’angolo: 7 celle. Il valore più piccolo dà un risultato peggiore: partendo da 1, i percorsi migliori sono 1, 2, 7, 8, 9 e 1, 6, 7, 8, 9, con 5 celle ciascuno.

+18 test nascosti all’invio

Per approfondire

Puoi restituire anche le celle di uno dei percorsi più lunghi, non solo la sua lunghezza?

Soluzione

Traccia una freccia da ogni cella verso ciascuna cella adiacente che contiene un valore maggiore. I valori aumentano lungo ogni freccia, quindi nessuna catena di frecce può tornare al punto di partenza: la griglia è un grafo diretto aciclico e il compito consiste nel trovare il suo cammino più lungo. In un grafo generico, questo problema è irrisolvibile per input di grandi dimensioni, ma, in assenza di cicli, il cammino più lungo da una cella dipende solo da quella cella: lo calcoli una volta per cella e l’intero problema si riduce a O(m × n). La ricerca in profondità con memoizzazione lo calcola dall’alto verso il basso; eliminando le celle dalla griglia a partire dai picchi, l’algoritmo di Kahn al contrario lo calcola dal basso verso l’alto.

Segui ogni percorso crescente

Corretto, ma non termina sui test più grandi

Intuizione

Inizia una camminata da ogni cella. Dalla cella in cui ti trovi, prova ciascuna delle quattro celle vicine con un valore maggiore e, da lì, continua nello stesso modo finché non rimane nessuna cella vicina con un valore maggiore. Conta le celle di ogni camminata e conserva il conteggio più alto.

La camminata non ha bisogno di un insieme di celle visitate. I valori aumentano a ogni passo, quindi la camminata non può mai tornare a una cella: per ritrovarsi su quella cella dovrebbe scendere di nuovo fino al suo valore. Tieni le camminate su uno stack di elementi (cella, lunghezza). Estrarre un elemento termina una camminata in quella cella, mentre inserire le celle vicine con valori maggiori la prolunga.

Il metodo è corretto, ma disperatamente lento, perché le camminate si diramano. In una griglia di 100 × 100 in cui ogni valore è la somma della sua riga e della sua colonna, ogni passo a destra o in basso fa aumentare il valore, e le sole camminate dall’angolo in alto a sinistra sono più di 10^58. Peggio ancora, la camminata da una qualsiasi cella viene ripetuta ogni volta che un’altra camminata la attraversa: è proprio questo spreco che il prossimo approccio elimina.

Algoritmo

Per ogni cella, inserisci (quella cella, 1) in una pila.
Estrai una voce (cella, lunghezza) e aggiorna la risposta con lunghezza.
Inserisci (vicino, lunghezza + 1) per ogni vicino all'interno della griglia con un valore strettamente maggiore.
Ripeti finché la pila non è vuota, poi passa alla cella iniziale successiva.
Restituisci la lunghezza massima trovata.

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

Ricerca in profondità con memoizzazione e uno stack personalizzato

Intuizione

Sia best[cell] il numero di celle nel percorso crescente più lungo che inizia da quella cella. Il percorso termina lì oppure il passo successivo va a una vicina più grande e continua lungo il percorso più lungo da quella vicina. Quindi best[cell] = 1 + max(best[nb]) tra le vicine più grandi nb, oppure 1 se non ce ne sono. È sicuro riutilizzare questo valore grazie alla struttura aciclica: le celle che precedono cell in qualsiasi percorso sono tutte più piccole, quindi non possono mai comparire dopo di essa, e la continuazione migliore da cell è la stessa indipendentemente da come ci sei arrivato. Calcola ogni best una sola volta e memorizzalo: l’albero esponenziale dei percorsi si riduce a una visita per cella.

Nel primo esempio, 9 non ha vicine più grandi, quindi lì best è 1. Poi 8 ottiene 2, 7 ottiene 3, 6 e 2 ottengono 4, 5 e 1 ottengono 5, 4 ottiene 6 e 3 ottiene 7, che è la risposta. Ogni cella esamina le sue 4 vicine, quindi il lavoro è O(m × n).

Il codice naturale è ricorsivo: una funzione che restituisce best per una cella, richiamando se stessa per ogni vicina più grande. La profondità delle chiamate è uguale alla lunghezza del percorso seguito e i vincoli consentono un percorso che attraversa ogni cella: valori che serpeggiano avanti e indietro su una griglia 100 × 100 formano un unico percorso di 10,000 celle, mentre Python si ferma per impostazione predefinita dopo 1,000 chiamate annidate. Il codice qui sotto esegue direttamente la ricorsione, quindi nessun percorso è troppo lungo per lui. Tieni uno stack di celle e, per ogni cella, il numero di direzioni su quattro che hai provato. Guarda la cella in cima: se le resta una direzione, provala e inserisci nello stack la vicina in quella direzione quando è più grande e non è ancora terminata. Quando hai provato tutte e quattro le direzioni, tutte le vicine più grandi sono terminate; quindi estrai la cella e imposta il suo best. È esattamente l’ordine che seguirebbe una chiamata ricorsiva.

La ricerca non ha bisogno di un contrassegno «in corso», a differenza del rilevamento dei cicli. Ogni cella nello stack è più grande di quella sottostante, quindi una vicina più grande della cella in cima non può trovarsi più in basso nello stack.

Algoritmo

Imposta best a 0 (non ancora noto) e un contatore delle direzioni a 0 per ogni cella.
Per ogni cella con best pari a 0, inseriscila in uno stack.
Guarda la cella in cima. Se ha una direzione a sinistra, incrementa il suo contatore e inserisci la cella vicina in quella direzione se si trova all’interno della griglia, è più grande e non è stata completata.
Se sono state provate tutte e quattro le direzioni, estrai la cella dallo stack e imposta best a 1 più il valore best più grande tra quelli dei suoi vicini più grandi, oppure a 1 se non ne ha.
Restituisci il valore best più grande.

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

Sbuccia la griglia dalle sue cime

Intuizione

Capovolgi la programmazione dinamica e costruiscila dai valori più alti verso il basso, come l’algoritmo di Kahn costruisce un ordinamento topologico. Chiama una cella picco quando nessun vicino è più grande. Da un picco non è possibile proseguire lungo il percorso, quindi questo contiene 1 cella. Rimuovi tutti i picchi in una volta: questo è il livello 1. Ora alcune celle hanno perso il loro ultimo vicino più grande, quindi sono picchi tra quelle rimaste. Rimuovile come livello 2 e continua finché la griglia non è vuota. Il numero di livelli è la risposta.

Perché: una cella si trova nel livello k esattamente quando il percorso più lungo che parte da essa contiene k celle. Una cella viene rimossa nel turno successivo a quello in cui viene rimosso il suo ultimo vicino più grande, quindi il suo livello è 1 più il livello più alto tra i suoi vicini più grandi, che è la formula best[cell] = 1 + max(best[nb]) dell’approccio precedente. Il livello più profondo corrisponde all’inizio di un percorso più lungo.

Nel primo esempio, l’unico picco è il 9 (i suoi vicini sono 8 e 2). Rimuovendolo si libera l’8; rimuovendo l’8 si libera il 7; rimuovendo il 7 si liberano il 2 e il 6; questi due liberano l’1 e il 5; il 5 libera il 4 e il 4 libera il 3. Sono 7 livelli, e il percorso 3, 4, 5, 6, 7, 8, 9 sale passando per una cella di ciascun livello.

Per trovare rapidamente il livello successivo, conta per ogni cella quanti vicini più grandi ha ancora. Rimuovere una cella diminuisce il conteggio di ogni vicino strettamente più piccolo; quando il conteggio raggiunge 0, quel vicino entra nel livello successivo. Ogni cella viene rimossa una volta e ogni coppia di vicini viene esaminata un numero costante di volte, quindi il lavoro è O(m × n), senza stack e senza ricorsione.

Algoritmo

Per ogni cella, conta i vicini con un valore maggiore.
Inserisci nel livello corrente ogni cella il cui conteggio è 0.
Finché il livello non è vuoto, incrementa di 1 il conteggio dei livelli. Per ogni cella al suo interno, diminuisci il conteggio di ogni vicino strettamente più piccolo e inserisci nel livello successivo un vicino il cui conteggio raggiunge 0.
Imposta il livello successivo come quello corrente e ripeti.
Restituisci il conteggio dei livelli.

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

Trappole e casi limite

Gli errori qui derivano dalla parola «strettamente», dalla ricorsione profonda e dalle abitudini acquisite con altri problemi sulle griglie.

Confrontare con >= invece di >. Con due 4 adiacenti, ciascuno conta come un passo in salita rispetto all’altro, le frecce formano un ciclo, una ricerca esaustiva va avanti e indietro all’infinito e una ricerca con memoizzazione legge una lunghezza che è ancora in fase di calcolo.
Ricorsione su percorsi molto lunghi. Una ricerca ricorsiva raggiunge una profondità pari alla lunghezza del percorso, e i vincoli consentono un percorso che attraversa ogni cella: valori che si snodano avanti e indietro su una griglia 100 × 100 formano un percorso di 10.000 celle, dieci volte il limite predefinito di Python di 1.000 chiamate annidate. Percorsi così lunghi richiedono una ricerca iterativa con uno stack personalizzato o un limite di ricorsione aumentato (sys.setrecursionlimit in Python); anche un limite molto alto può comunque causare l’overflow dello stack interno dell’interprete.
Saltare le celle già visitate, come fa una visita flood fill. Raggiungere una cella già elaborata non è un vicolo cieco: la sua lunghezza memorizzata è esattamente ciò di cui ha bisogno la cella corrente. Leggila, non saltarla.
Partire solo dal valore più piccolo. Nel primo esempio, partendo da 1 si ottengono 5 celle, ma la risposta, 7, parte da 3. Il percorso più lungo può iniziare da qualsiasi cella che non ha vicini più piccoli, e possono essercene molte.
Restituire 0. Ogni cella costituisce un percorso di 1 cella, quindi una griglia con valori tutti uguali, o una griglia 1 × 1, ha risposta 1. Imposta la lunghezza di ogni cella a 1, non a 0.
Nell’approccio di eliminazione progressiva, diminuire il conteggio di un vicino uguale. Solo un vicino strettamente più piccolo ha perso un vicino più grande.

Domande frequenti4

Qual è la complessità temporale del percorso crescente più lungo in una matrice?

Tempo O(m × n) e spazio O(m × n) con una ricerca in profondità memorizzata o con l'eliminazione topologica. Ognuna delle m × n celle viene completata una volta e esamina i suoi 4 vicini un numero costante di volte, e ogni metodo mantiene un numero per cella. Provare ogni percorso da ogni cella è invece esponenziale: su una griglia 100 × 100 in cui ogni valore è la somma della riga e della colonna, più di 10^58 percorsi partono dall'angolo in alto a sinistra.

Perché questo problema non ha bisogno di un insieme dei nodi visitati?

Un percorso che sale soltanto non può mai tornare a una cella, perché dovrebbe ridiscendere fino al valore di quella cella. Quindi la regola della stretta crescita vieta già di ripassare sulle celle e il grafo dei passaggi non contiene cicli. Ecco perché anche la memoizzazione è sicura: le celle precedenti a una determinata cella non possono interferire con il percorso successivo.

Il problema del percorso crescente più lungo in una matrice è un problema di programmazione dinamica o un problema di grafi?

Entrambi. È il percorso più lungo in un grafo aciclico diretto, ovvero programmazione dinamica su un ordine topologico: la risposta per una cella è 1 più la migliore risposta tra quelle delle sue celle adiacenti con valore maggiore. La ricerca in profondità con memoizzazione riempie la tabella nell'ordine in cui la ricerca termina l'elaborazione delle celle, mentre l'eliminazione topologica la riempie livello per livello, partendo dai picchi. Ordinare le celle in base al valore, dal più grande al più piccolo, fornisce un terzo ordine valido, al costo di O(m × n × log(m × n)) per l'ordinamento.

In che cosa differisce dalla sottosequenza crescente più lunga?

Una sottosequenza può saltare degli elementi e deve mantenerne l’ordine, mentre qui un percorso deve spostarsi su una cella adiacente, in una qualsiasi delle quattro direzioni. Il problema della sottosequenza si risolve con la programmazione dinamica su una linea; questo invece si risolve con la programmazione dinamica su una griglia trasformata in un grafo. Entrambi si basano sullo stesso fatto: una catena strettamente crescente non può mai ripiegare su sé stessa.

Python

def longestIncreasingPath(matrix):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso

Longest Increasing Path in a Matrix

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Segui ogni percorso crescente

Ricerca in profondità con memoizzazione e uno stack personalizzato

Sbuccia la griglia dalle sue cime

Trappole e casi limite

Domande frequenti4

Problemi simili