Percorsi unici e somma minima dei percorsi nelle griglie

Unique Paths (LeetCode 62) chiede: in una griglia m×n, quanti percorsi distinti vanno dall'angolo in alto a sinistra a quello in basso a destra, se ci si può muovere solo a destra o verso il basso? Per una griglia 3×7 la risposta è 28. L'intuizione chiave è che ogni percorso verso la cella (i,j) deve provenire da (i-1,j) (dall'alto) oppure da (i,j-1) (da sinistra), dando luogo a una formulazione naturale della DP 2D.

Si definisca dp[i][j] come il numero di percorsi che portano alla cella (i,j). La prima riga e la prima colonna contengono solo 1 (c'è un solo modo per raggiungere ogni cella della riga superiore o della colonna più a sinistra). Per le altre celle: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Si riempia la tabella riga per riga; la risposta è dp[m-1][n-1]. Complessità temporale: O(m×n); spazio: O(m×n), riducibile a O(n).

Poiché dp[i][j] dipende solo dalla riga corrente e da quella precedente, è possibile sostituire l'intera tabella 2D con un singolo array 1D. Si inizializzino tutti i valori a 1, quindi, per ogni riga, li si aggiorni sul posto: dp[j] += dp[j-1]. Dopo aver elaborato la riga i, dp[j] contiene il valore che nella tabella 2D era dp[i][j]. Questo è un comune schema di ottimizzazione per i problemi di DP 2D.

Unique Paths II (LeetCode 63) aggiunge ostacoli (celle contrassegnate con 1) alla griglia. Qualsiasi percorso che attraversi un ostacolo non è valido, quindi dp[i][j] = 0 se obstacle[i][j] == 1. Altrimenti, la ricorrenza rimane la stessa: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Se la partenza o la destinazione è bloccata, il risultato è immediatamente 0. Si inizializzino con attenzione i casi base: una volta incontrato un 1 nella prima riga o nella prima colonna, tutte le celle successive di quella riga o colonna valgono 0.

Minimum Path Sum (LeetCode 64) chiede: data una griglia m×n contenente interi non negativi, si trovi il percorso dall'angolo in alto a sinistra a quello in basso a destra che minimizza la somma di tutti i numeri lungo il percorso (muovendosi solo a destra o verso il basso). Ad esempio, nella griglia [[1,3,1],[1,5,1],[4,2,1]], il percorso 1→3→1→1→1 dà come somma 7. Lo stato DP è lo stesso dei percorsi unici, ma ora la ricorrenza usa il minimo invece della somma.

Si definisca dp[i][j] come il costo minimo per raggiungere la cella (i,j). Caso base: dp[0][0] = grid[0][0]. Prima riga: dp[0][j] = dp[0][j-1] + grid[0][j] (l'unico percorso possibile proviene da sinistra). Prima colonna: dp[i][0] = dp[i-1][0] + grid[i][0] (l'unico percorso possibile proviene dall'alto). Caso generale: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Questa è una traduzione diretta del principio di ottimalità.

Se è consentito modificare la griglia di input, è possibile aggiornarla sul posto per evitare di allocare una tabella DP separata. In questo modo lo spazio ausiliario si riduce a O(1) (oltre allo spazio dell'input). Nei colloqui può capitare che venga chiesta questa ottimizzazione: si chiarisca se è consentito modificare l'input prima di procedere. In caso contrario, il trucco dell'array scorrevole 1D consente di usare spazio O(n) senza modificare l'input.

Triangle (LeetCode 120) chiede la somma minima del percorso dalla cima alla base di un array a forma di triangolo, dove ogni passo porta a un numero adiacente nella riga sottostante. La DP dal basso verso l'alto è la soluzione più semplice: si parte dalla penultima riga e, per ogni cella, si aggiunge il minimo dei due valori direttamente sottostanti. In questo modo non è necessario tenere traccia degli indici di partenza e la risposta risale naturalmente fino all'apice.

Dungeon Game (LeetCode 174) chiede la salute iniziale minima necessaria per salvare una principessa nell'angolo in basso a destra di una griglia con celle negative (danno) e positive (guarigione). È necessario muoversi a destra o verso il basso. Il trucco consiste nel riempire la tabella DP a ritroso (dall'angolo in basso a destra a quello in alto a sinistra), calcolando la salute minima necessaria in ogni cella. Per ogni cella: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). La salute deve rimanere sempre almeno pari a 1.

I problemi di DP su griglia condividono la stessa struttura, ma differiscono per la direzione di riempimento e per l'operazione di transizione: Unique Paths usa la somma (conta tutti i modi). Min Path Sum usa il minimo (ottimizza). Dungeon Game si riempie a ritroso (calcola la salute necessaria in base al futuro). Quando si affronta un nuovo problema di DP su griglia, ci si chieda: (1) che cosa rappresenta ogni cella? (2) in quale direzione devo riempire la tabella? (3) quale operazione combina i valori vicini? Le risposte a queste tre domande rivelano l'intera soluzione.

Tutti i problemi di DP su griglia presentati qui richiedono tempo O(m×n). Lo spazio varia da O(m×n) per una tabella completa fino a O(n) con un array scorrevole 1D, e a O(1) di spazio ausiliario quando la griglia può essere modificata sul posto. Nei colloqui, si menzioni l'ottimizzazione a spazio O(n) dopo aver presentato la soluzione O(m×n): dimostra la consapevolezza dei compromessi. Per tutti i problemi, si valuti anche l'eventuale esistenza di una scorciatoia greedy (come la formula matematica per i percorsi unici).

Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.

In questa lezione ha imparato che: Unique Paths riempie una tabella 2D con dp[i][j] = dp[i-1][j] + dp[i][j-1] e può essere calcolato in O(1) usando la combinatoria, Min Path Sum usa la stessa struttura, ma sostituisce la somma con min per ottenere il costo ottimale del percorso e tutti i problemi di DP su griglia condividono lo schema di definire uno stato per ogni cella e scegliere un operatore di transizione (somma, minimo, massimo). Ora passeremo alla sottosequenza comune più lunga usando la DP 2D su due sequenze.