Pattern nella programmazione dinamica - 2

Dichiarazione di non responsabilità: il metodo descritto di seguito non è universale, ma spesso può risolvere un problema o aiutarti a trovare la soluzione giusta.

Se un problema ti chiede di distruggere/comprimere/unire in modo ottimale (o simili) un array, allora dovresti provare a risolverlo usando la programmazione dinamica sui sottosegmenti.

Prendiamo dp[l][r] - la risposta ottimale per un sottosegmento con indici da l a r. Il ricalcolo delle dinamiche dipende fortemente dall'attività, ma ci sono le seguenti idee generali:

1) Guarda gli elementi estremi l e r. Se corrispondono o si completano in qualche altro modo, molto probabilmente sarà possibile aggiornare il valore di dp[l][r] tramite dp[l+1][r-1]. Altrimenti tramite dp[l][r-1] o dp[l+1[r].

2) Accade spesso che il segmento [l;r] non possa essere rappresentato attraverso un'unica costruzione. Quindi è necessario considerare tutte le possibili sezioni di questo sottosegmento in due parti, cioè iterare sull'elemento k da l a r-1 e ricalcolare dp[l][r] attraverso dp[l][k] e dp[ k+1][r] . Nei sottosegmenti più piccoli, anche queste sezioni sono state ordinate, quindi, infatti, vengono prese in considerazione le opzioni per dividere il sottosegmento [l;r] non solo in due parti, ma in qualsiasi numero di esse.
 

Dichiarazione di non responsabilità: il metodo descritto di seguito non è universale, ma spesso può risolvere un problema o aiutarti a trovare la soluzione giusta.

Se hai bisogno di verificare l'esistenza di una permutazione in un problema, o trovare il numero di permutazioni che corrispondono, o qualcosa di simile, allora dovresti prendere in considerazione l'utilizzo della programmazione di sottoinsiemi dinamici.

Il parametro principale sarà una maschera di bit, che mostrerà quali elementi sono già stati inclusi nella permutazione e quali no. Inoltre spesso è richiesto un secondo parametro che indichi quale elemento è stato incluso per ultimo.

Spesso le permutazioni possono essere viste nel contesto dei percorsi nei grafici. Di conseguenza, consideriamo un esempio classico: il problema del percorso hamiltoniano.
Un cammino hamiltoniano è un cammino semplice che attraversa ogni vertice del grafo esattamente una volta. Può essere rappresentato semplicemente come una permutazione di lunghezza n, dove n è il numero di vertici. L'ordine all'interno di questa permutazione indicherà l'ordine in cui vengono attraversati i vertici in questo percorso.

Per verificare la presenza di un percorso hamiltoniano nel grafico, iniziamo la dinamica dp[mask][last] - esiste un percorso semplice che ha aggirato i vertici contrassegnati con quelli nella maschera di bit ed è finito all'ultimo vertice.
I valori iniziali saranno dp[2ⁱ][i] = true, il resto false, il che significa che c'è sempre un percorso vuoto che inizia in uno qualsiasi dei vertici.
Avendo il valore true in dp[mask][last] faremo delle transizioni in avanti, nel senso di "estendere il percorso". Cioè, cercheremo i numeri di vertici che sono contrassegnati con zero nella maschera (non li abbiamo ancora visitati per strada) e allo stesso tempo tale che ci sia un bordo dall'ultimo a questo vertice (il percorso deve essere esteso da un bordo esistente). Cioè, facciamo dp[mask | 2^k][k] = true se dp[mask][last] = true AND mask & 2^k = 0 (il vertice k non è stato ancora visitato) E c'è un ultimo spigolo -> k.
In definitiva, esiste un percorso hamiltoniano se esiste un valore vero in dp per i parametri della maschera di bit tutti uno e per ogni ultimo vertice.