dynamische Programmierübung zum Schneiden von Saiten

Ich habe an dem folgenden Problem aus diesem Buch gearbeitet .

Eine bestimmte Zeichenkettenverarbeitungssprache bietet eine primitive Operation, die eine Zeichenkette in zwei Teile aufteilt. Da bei dieser Operation die ursprüngliche Zeichenfolge kopiert wird, werden für eine Zeichenfolge mit der Länge n unabhängig von der Position des Schnitts n Zeiteinheiten benötigt. Angenommen, Sie möchten eine Zeichenfolge in viele Teile teilen. Die Reihenfolge der Pausen kann sich auf die Gesamtlaufzeit auswirken. Wenn Sie beispielsweise eine Zeichenfolge mit 20 Zeichen an den Positionen und ausschneiden möchten, verursacht der erste Schnitt an Position Gesamtkosten von , während Position 10 zuerst bessere Kosten von .10 3 20 + 17 = 37 20 + 10 = $3$$10$$3$$20 + 17 = 37$$20 + 10 = 30$

Ich brauche einen dynamischen Programmieralgorithmus, der bei Schnitten die minimalen Kosten für das Schneiden eines Strings in Stücke ermittelt.m + $m$$m +1$

Die Grundidee ist: Probieren Sie alle Schnittpositionen als erste Wahl aus, lösen Sie die jeweiligen Teile rekursiv, addieren Sie die Kosten und wählen Sie das Minimum.

In der Formel:

$\qquad \displaystyle \operatorname{mino}(s, C) = \begin{cases} |s| &, |C| = 1 \\ |s| + \min_{c \in C} \left[ \begin{align}&\operatorname{mino}(s_{1,c}, \{c' \in C \mid c' < c\})\ \\ +\ &\operatorname{mino}(s_{c+1,|s|}, \{c' - c \in C \mid c' > c\}) \end{align}\right] &, \text{ else} \end{cases}$

Beachten Sie, dass das Anwenden von Memo auf diese Rekursion tatsächlich Arbeit spart, da das Umschalten der Reihenfolge nacheinander angewendeter Schnittpaare dazu führt, dass dieselben drei Teilprobleme gelöst werden.

Es ist immer eine gute Idee, zuerst einen rekursiven Algorithmus zu finden und ihn dann in eine Tabelle umzuwandeln.

1. $f(C,n)$
2. $~~$ if (C = ) gibt 0 zurück;$\emptyset$
3. $~~$ sonst
4. $~~~~$ opt = unendlich;
5. $~~~~$für jedes tun$c\in C$
6. $~~~~~~D=\{d\in C:d<c\}$
7. $~~~~~~E=\{e-c:e\in D,e>c\}$
8. $~~~~~~opt = min\{opt,f(D,c)+f(E,n-c)\}$
9. $~~~~$$opt+n$

$n \choose 2$$E$$f$

Dies ist Quicksort in einem Multiset sehr ähnlich. Es ist optimal, wenn der Schnittpunkt der Mitte am nächsten liegt.

$s_k$