House Robber: ricorrenza prendi o salta

Il problema del ladro di case chiede: dato un array di interi non negativi che rappresentano la somma di denaro presente in ogni casa, qual è la somma massima che è possibile rubare senza derubare due case adiacenti? Ad esempio, [2, 7, 9, 3, 1] restituisce 12, derubando le case 0, 2 e 4. È un classico problema di DP 1D in cui a ogni passaggio si prende una decisione binaria.

Sia dp[i] la somma massima rubata dalle prime i+1 case. Per ogni casa i si hanno due possibilità: saltarla, prendendo dp[i-1], oppure derubarla, prendendo nums[i] + dp[i-2]. La ricorrenza è dp[i] = max(dp[i-1], nums[i] + dp[i-2]). Questo è il modello fondamentale prendi o salta, che ricorre in molti problemi di DP.

Per [2, 7, 9, 3, 1], ripercorriamo la tabella: dp[0] = 2, dp[1] = max(2, 7) = 7, dp[2] = max(7, 9+2) = 11, dp[3] = max(11, 3+7) = 11, dp[4] = max(11, 1+11) = 12. La risposta finale è dp[4] = 12. Ripercorrere manualmente la tabella conferma che la ricorrenza gestisce correttamente sia la scelta di prendere sia quella di saltare a ogni posizione.

La tabella DP guarda solo due posizioni indietro, quindi è possibile sostituire l'intero array con due variabili: prev2, che rappresenta il valore di due passaggi precedente, e prev1, quello di un passaggio precedente. Dopo ogni iterazione si esegue lo scorrimento: prev2 = prev1 e prev1 = current. In questo modo la memoria si riduce da O(n) a O(1), mantenendo la complessità temporale O(n).

Si esegua sempre il test della soluzione sui casi limite: un array vuoto, che restituisce 0; un array con un solo elemento, che restituisce quell'elemento; e un array con due elementi, che restituisce il maggiore dei due. Durante un colloquio, menzionare e gestire questi casi dimostra accuratezza. Il controllo if n == 1 impedisce l'accesso fuori dai limiti dell'array quando si accede a nums[1] per calcolare dp[1].

La variante circolare (LeetCode 213) dispone le case in cerchio, rendendo adiacenti la prima e l'ultima. Non è possibile applicare direttamente la ricorrenza lineare. L'intuizione chiave è la seguente: o si deruba la prima casa escludendo l'ultima, oppure si esclude la prima includendo l'ultima. Si esegue l'algoritmo lineare del ladro di case su entrambi i sottoarray e si prende il massimo.

Un approccio greedy ingenuo potrebbe tentare di derubare sempre la casa disponibile con il valore maggiore. Tuttavia, fallisce su input come [2, 1, 1, 2]: l'approccio greedy sceglie la casa 0, di valore 2, e poi la casa 3, anch'essa di valore 2, per un totale di 4, mentre derubare le case 0 e 2 dà anch'esso 3. Aspetti — in questo caso l'approccio greedy funziona! Si provi però [1, 3, 1, 3, 100]: l'approccio greedy sceglie i valori 3 e 3, agli indici 1 e 3, ottenendo 6, e non considera la soluzione ottimale 1+1+100=102. La DP è necessaria perché scelte ottimali localmente non garantiscono un ottimo globale.

Il modello prendi o salta si generalizza oltre il problema del ladro di case. Ogni volta che si scorre un array e a ogni posizione si sceglie tra includere l'elemento corrente, saltando quello precedente, oppure escluderlo, mantenendo il risultato precedente, si è di fronte a una DP prendi o salta. Vincoli come nessun elemento adiacente o nessun intervallo sovrapposto indicano che è opportuno applicare questo modello.

Delete and Earn (LeetCode 740) chiede: per ogni numero scelto si guadagna num × count(num), ma è necessario eliminare tutte le occorrenze di num-1 e num+1. Il problema si riduce direttamente a quello del ladro di case: si costruisce un array earn[v] = v × count(v) per tutti i valori, quindi si esegue l'algoritmo del ladro di case su questo array. Riconoscere queste riduzioni è una competenza fondamentale nei colloqui.

In Ladro di case III, le case sono disposte in un albero binario. Non è possibile derubare contemporaneamente un nodo e il suo genitore diretto. Si definisca una funzione helper che restituisce due valori: rob(node) → (rob_root, skip_root). Se si deruba la radice, si sommano i valori skip dei due figli. Se si salta la radice, si somma il valore migliore di ciascun figlio. Si tratta di una DFS post-order con una decisione prendi o salta a ogni nodo.

La versione lineare del problema del ladro di case richiede O(n) tempo e O(1) spazio grazie all'ottimizzazione con due variabili. Anche la variante circolare richiede O(n) tempo, perché richiama due volte la versione lineare. La variante su albero richiede O(n) tempo e O(h) spazio, dove h è l'altezza dell'albero. Durante un colloquio, dichiari sempre la complessità dopo aver scritto il codice e menzioni l'ottimizzazione dello spazio: dimostra che sa andare oltre una prima soluzione funzionante.

Metta alla prova la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.

In questa lezione ha imparato: la ricorrenza di scelta o salto dp[i] = max(dp[i-1], nums[i] + dp[i-2]), la riduzione dello spazio O(n) a O(1) con due variabili a scorrimento ed estendere questo schema ad array circolari e alberi binari. Nella prossima lezione esamineremo i problemi Maximum Subarray e Maximum Product Subarray usando l'algoritmo di Kadane.