Risorse di programmazione dinamica in C?

Question

Scriverò domani il test Google online come un nuovo arrivato. Apparentemente, hanno sicuramente posto un problema sulla programmazione dinamica?

Qualcuno sa di una buona risorsa per la raccolta di problemi DP in C insieme a soluzioni? So cosa DP è & averlo usato in un'occasione o due volte. Tuttavia, mi sento di rompere un problema DP nel test, la pratica precedente di problemi tipici renderà più facile l'approccio.

Qualsiasi buona risorsa o set di problemi con soluzioni in C sarà molto apprezzato. Grazie.

Answer 1

Okay, quindi spero davvero che questo non contenga una "spudorata auto-promozione", dal momento che tutti questi link sono per codificare frammenti che ho postato sul mio sito personale. Se questo è inappropriato, per favore fatemelo sapere e posso portarli giù.

Ecco alcuni divertenti problemi DP che sono più o meno classici:

1. modifica minima distanza: Date due stringhe A e B, trovare il minor numero di modifiche (inserimenti, cancellazioni o sostituzioni) necessari per convertire A in B. Questo è chiamato la distanza di Levenshtein. (My solution)
2. Allineamento di sequenza ottimale: date due stringhe A e B, trova il numero minimo di spazi vuoti che devono essere inseriti nella sequenza per allineare A e B. Questo è chiamato l'algoritmo di Needleman-Wunsch. (My solution)
3. Percorsi più brevi a sorgente singola: Dato un grafico diretto G e un singolo nodo s, trovare le lunghezze dei percorsi più brevi da s a ciascun nodo nel grafico, assumendo che i bordi possono essere positivi o negativi ma che non esistono cicli . Questo è l'algoritmo di Bellman-Ford. (My solution)
4. Percorsi a coppie più brevi: Dato un grafico diretto G, trovare le distanze minime tra tutte le coppie di nodi. Questo è l'algoritmo di Floyd-Warshall. (My solution)

Speriamo che questo sia un po 'utile, e buona fortuna domani!

Answer 2

Il sito Web Topcoder è sorprendente. Non tutti i problemi usano DP, ma molti lo fanno. Accesso completo gratuito a tutti i problemi delle competizioni passate, che sono a 3 livelli di difficoltà differenti, così come le spiegazioni post-partita di ogni singolo problema dall'autore del problema. Non solo, ma è possibile recuperare rapidamente la soluzione del codice sorgente inviata da qualsiasi programmatore nella competizione.

Non sono tornato per un po ', ma consentono almeno C++, Java, C# e credo che molte altre lingue ora.

Answer 3

Ti suggerisco di raccogliere un libro "Un'introduzione agli algoritmi di bioinformatica". Questo ha un capitolo completamente su DP.As @templatetypedef menzionato Distanza di modifica minima, l'allineamento di sequenza ottimale ha altri problemi con loro. Anche se non c'è implementazione in esso. Devi farlo da solo. Ma troverai molto interessante leggerli.

Answer 4

Per esercitarti puoi prendere uno dei problemi disponibili su SPOJ. Per riconoscere facilmente quelli DP è possibile controllare a Problems Classifier (parola chiave: dp).