Lottando per comprendere il processo di pensiero richiesto per inventare alcune recidive per problemi di programmazione dinamici

cs.stackexchange https://cs.stackexchange.com/questions/119026

Domanda

Stavo facendo alcuni problemi di programmazione dinamica e sto lottando per capire il processo di pensiero richiesto per trovare le recidive.

Il primo problema che ho risolto era La più lunga sottostringa palindromica e sono riuscito a risolvere Usando con successo la seguente logica: ho una funzione f (I, J) che restituisce la più lunga sottostringa palindromica tra i personaggi nelle posizioni I, J nella stringa. Ho inventato la seguente ricorrenza: 

f(i,j) = true // if(s[i] = s[j])
f(i,j) = true // if(i>j) 
f(i,j) = true // if(s[i] = s[j] and f(i+1, j-1) == true)
f(i,j) = false // otherwise
.

Utilizzando questa ricorrenza Sono riuscito a risolvere il problema con successo.

.

Il secondo problema che volevo risolvere era parentesi validi più lunghi (che io Vuoi fare usando DP non pile). La domanda è: data una stringa contenente solo i personaggi '(' e ')', trova la lunghezza della sottostringa dei parentesi validi più lunghi.

Il mio processo di pensiero iniziale era che questo era simile al problema della sottostruttura palindromica più lunga che ho già risolto. Così ho definito f (i, J) come funzione che restituisce la parentesi valida più lunga tra elementi I, j. La ricorrenza che ho inventato è il seguente è il seguente - qui uso -1 per indicare che f (i, j) non forma una parentesi valida: 

f(i,j) = -1 // if i == j
f(i,j) = -1 // if j=i+1 and ! (s[i] = '(' and s[j] = ')')
f(i,j) = 2 // if j = i+1 and s[i] = '(' and s[j] = ')'
f(i,j) = 2 + f(i+1, j-1) if s[i] = '(' and s[j] = ')' and f(i+1, j-1) > 0;
f(i,j) = -1 // otherwise
.

Il mio codice (scritto in Java) per la versione top-down di quanto sopra è (Nota: DP [] [] è stato inizializzato in -2 che indica lo stato I, J non è ancora elaborato): 

private int topDown(String s, int i, int j, int[][] dp) {
    if(dp[i][j] != -2)
        return dp[i][j];

    if(i == j)
        dp[i][j] = -1;
    else if(j == i+1 && (s.charAt(i) != '(' || s.charAt(j) != ')' ) )
        dp[i][j] = -1;
    else if(j == i+1 && (s.charAt(i) == '(' && s.charAt(j) == ')' ) )
        dp[i][j] = 2;
    else if(s.charAt(i) == '(' && s.charAt(j) == ')' && topDown(s, i+1, j-1, dp) > -1)
        dp[i][j] = 2 + topDown(s, i+1, j-1, dp);
    else
        dp[i][j] = -1;

    return dp[i][j];
}
.

Questo non funziona per input come ()() in quanto restituirà 2 anziché 4.

.

Non sono riuscito a trovare una soluzione del mio, quindi ho cercato online. Ho trovato una soluzione qui < / a>.

In questo caso l'autore definisce f (i) come la lunghezza della parentesi più lunga più lunga più lunga, la sottostringa che inizia all'indice I. Quindi descrive la recidiva come segue: 

f(i) = 2 + f(i+2)   // if s[i] = "(" and s[i+1] = ")"
f(i) = f(i+1) + f(i + f(i+1) + 2)   // s[i]="(" AND s[i+1]="(" AND s[i+f(i+1)+1]=")"
f(i) = 0    // otherwise
.

Non ho scritto / testato il codice per la recidiva ma presumo che sia corretto.

.

Le mie domande sono le seguenti:

    .

  1. Quando stavo risolvendo il problema inizialmente non avevo pensato di scriverlo come una funzione di f (i). Ci ho pensato solo come funzione di f (I, J) e che si è rivelato sbagliato. Quindi c'è un modo semplice da raccontare solo guardando un problema quali stati dovrebbero essere calcolati? Ad esempio, perché non riesco a risolvere il problema della sottostruttura palindromica più lunga come funzione di f (i)? Allo stesso modo perché non riesco a risolvere il problema della parentesi più lungo come funzione di f (i, j)?

  2. C'è un modo per risolvere il problema di parentesi valido più lungo in funzione di F (I, J) in cui f (I, J) rappresenta la lunghezza della parentesi più lunga valida tra I e J? Va bene se la complessità runtime è più alta sono solo curioso di questo.

    3. Grazie.

È stato utile?

Soluzione

Ecco un modo per risolvere il problema delle parentesi valide più lunghe da parte della programmazione dinamica come sperava. O quasi.

Per semplicità, una stringa è chiamata valida se consiste in parentesi di apertura e chiusura ben formate.

L'osservazione critica è che una stringa è valida se è la stringa vuota, una concatenazione di due stringhe valide o "(" seguita da una stringa valida seguita da ")". In effetti, tale osservazione è la solita definizione ricorsiva di parentesi di apertura e chiusura ben formate! Questa osservazione indica che un insieme adatto di sottoproblemi è s[i...j].

.

Lascia che s sia la stringa data di lunghezza L.

    .

  • Lascia che dp sia un L mediante serie L+1 di Booleans.
    dp[i][j] diventerà true IFF La sottostringa s[i,j] è valida. Qui s[i,j] significa la sottostringa con indici da i comprensivi per j esclusivo, 0 <=i <= j < L. In particolare, s[i,i] significa la stringa vuota.

  • Inizialmente, tutto dp[i][j] è falso.

  • Il caso di base è la stringa vuota, dp[i][i] = true per tutti i i.

  • La relazione di ricorrenza è, in base all'osservazione sopra, dp[i][j] = true per i < j se s[i] == '(' e dp[i+1][j-1] == true e s[j-1] == ')' o c'è un indice k, tale che sia dp[i][k] == true e dp[k][j] == true. Possiamo stipulare quel i < k < j.

.

Ecco la versione top-down dell'approccio di cui sopra, seguendo lo stile nella domanda. 

private static boolean topDown(String s, int i, int j, Boolean[][] dp) {
    if (i > j) return false;
    if (dp[i][j] != null) return dp[i][j];

    if (i == j) {
        dp[i][i] = true;
    } else {
        if (s.charAt(i) == '(' && s.charAt(j - 1) == ')' && topDown(s, i + 1, j - 1, dp)) {
            dp[i][j] = true;
        } else {
            for (int k = i + 1; k < j; k++) {
                if (topDown(s, i, k, dp) && topDown(s, k, j, dp)) {
                    dp[i][j] = true;
                }
            }
        }

    }

    if (dp[i][j] != null) {
        return true;
    } else {
        dp[i][j] = false;
        return false;
    }
}
.

.

Ecco la versione Bown-up. Il codice è impegnato un po 'dall'osservazione che una stringa può essere valida solo quando la sua lunghezza è pari. 

private static int longestValidSubstring(String s) {
    final int L = s.length();

    // isValid[i][j] is true iff s.substring(i,j) is valid.
    boolean[][] isValid = new boolean[L][L + 1];

    // empty string is valid.
    for (int i = 0; i < L; i++) {
        isValid[i][i] = true;
    }
    for (int l = 2; l <= L; l += 2) {  // l is the length
        for (int i = 0; i <= L - l; i++) {
            // determine isValid[i][i+l]
            if (s.charAt(i) == '(' && s.charAt(i + l - 1) == ')' && isValid[i + 1][i + l - 1]) {
                isValid[i][i + l] = true;
            } else {
                for (int j = 2; j < l; j += 2) {
                    if (isValid[i][i + j] && isValid[i + j][i + l]) {
                        isValid[i][i + l] = true;
                        break;
                    }
                }
            }
        }
    }

    for (int l = L & 0xfffffffe; l >= 2; l -= 2) {
        for (int i = 0; i <= L - l; i++) {
            if (isValid[i][i + l]) {
                return l;
            }
        }
    }
    return 0;
}
.

.

La versione iterativa dovrebbe essere più veloce della versione top-down. Tuttavia, anche la versione iterativa non è abbastanza veloce quando L è grande dal momento che calcola le voci di L * L, che è piuttosto grande una volta che L è superiore a 10000. Inoltre, anche l'array tridimensionale isValid utilizza anche molta memoria.

qui e qui sono due soluzioni ulteriormente ottimizzate. Non li discuterò, poiché sono fuori dallo scopo di questa risposta.

.
.

C'è un modo per risolvere il problema dei parentesi validi più lunghi in funzione di F (I, J) in cui f (I, J) rappresenta la lunghezza delle parentesi valide più lunghe tra i e J? Va bene se la complessità runtime è più alta, sono solo curioso di questo.

La qualità fondamentale dei sottoproblemi nella programmazione dinamica è che è possibile risolvere un subproblem più grande più facilmente dopo aver avuto la soluzione al subproblem più piccolo. Oppure, è possibile estendere o combinare le soluzioni ai sottoproblemi più piccoli per creare una soluzione al problema più grande.

In questo particolare problema, se sappiamo se tutte le sottostringhe più corte siano valide o meno, è facile conoscere una sottostringa più lunga che è leggermente più lunga è valida o meno. D'altra parte, se conosciamo tutto f (I, J), che rappresentano la lunghezza della sottostrutturazione valida più lunga tra I e J, la mancanza di una posizione specifica di quelle sottostrinimenti valide più lunghe non aiutano a determinare se una sottostringa di un La sottostringa è valida o meno. La differenza è fondamentale, anche se potrebbe essere sottile per gli occhi non addestrati. Imparerai ad apprezzare la differenza.

.

Quando stavo risolvendo il problema inizialmente non avevo pensato di scriverlo come funzione di f (i). Ci ho pensato solo come funzione di f (I, J) e che si è rivelato sbagliato. Quindi c'è un modo semplice da raccontare solo guardando un problema quali stati dovrebbero essere calcolati? Ad esempio, perché non riesco a risolvere il problema della sottostruttura palindromica più lunga come funzione di f (i)? Allo stesso modo perché non riesco a risolvere il problema della parentesi più lungo in funzione di f (i, j)?

Come ho mostrato sopra, non è necessariamente sbagliato usare f (i, j) anche se dovremmo dare f (i, j) un significato leggermente diverso. Risolvere un problema in modo efficiente potrebbe non essere facile, anche se è noto per essere risolvibile dalla programmazione dinamica. Abbastanza alcuni problemi che mi puzzino per molto tempo anche se mi considero sperimentato. Richiede qualche intelligenza ed esperienza per identificare o formulare il set corretto di sottoproblemi (che non sono necessariamente nella forma esatta del problema originale).

Per estendere una sottostringa palindromica a una sottostringa palindromica più lunga, è necessario estenderla da entrambi i lati. Che indica che potrebbe non essere facile risolvere il problema della sottostruttura palindromica più lunga in funzione di una singola variabile che rappresenta un'estremità del palindromi

C Stringa in modo semplice ed efficiente.Tuttavia, se analizziamo la struttura raffinata dei palindromi, potremmo arrivare al Algoritmo di Manacher , che usa fondamentalmente una mappa da una singola variabile che rappresenta il punto centrale delle sottostringhe palindromiche.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top