Dynamische Programmierung einer Anzahl von Subsequenzen mit der Eigenschaft?

Question

Betrachten Sie ein dynamisches Programmierproblem, das fragt, wie viele verschiedene Untersequenzen (nicht notwendigerweise zusammenhängend) einer Sequenz S eine bestimmte Eigenschaft P mit dem Wert p0 haben.

Der Bereich P ist klein und endlich, und es ist eine effiziente Art und Weise der Berechnung der P:

P(s1 + s2) = f(P(s1), P(s2)) 

wo + bezeichnet Sequenz Verkettung.

Ein Weg, um dies zu tun wäre zu zählen, wie viele Teilfolgen gibt es das Präfix S[1] + S[2] + ... + S[k] von S, die Eigenschaft px haben. (Bewahren Sie diese in Count[px][k])

So ist die Rekursion ist:

Count[px][k] = Count[px][k-1] // not using element S[k]; 

P pq = f(px,P(S[k])); // calculate property pq of appending element S[k] 
Count[pq][k] += Count[px][k-1] // add count of P(prefix+S[k]) 

und die Antwort lautet dann:

return Count[p0][S.length] 

Dies funktioniert, wenn die Elemente von S paarweise verschieden sind, aber es wird zählen zwei Untersequenzen, die den gleichen Wert haben, aber unterschiedliche Elemente mit unterschiedlichen Positionen verwenden.

Wie kann ich diesen Algorithmus so ändern, dass er genau eine Teilsequenz genau einmal zählt? (dh zählt nur distinkte Subsequenzen)

Answer 1

Angenommen, die Sequenz besteht aus Zeichen und S [k] ist der Buchstabe x.

Das Problem ist, dass Sie alle Sequenzen, die S [k] nicht verwenden, doppelt gezählt haben, aber dennoch mit x enden (das kann nur passieren, wenn x früher in der Sequenz passiert ist).

Angenommen, das letzte Mal, dass x auftauchte, war am Element S [j]. Alle eindeutigen Sequenzen, die mit x enden, werden einfach durch Zählen aller verschiedenen Sequenzen bis zur Position j-1 und anschließendes Addieren von x auf alle angegeben.

Wir können daher die Doppelzählung korrigieren, indem wir diese Zahl subtrahieren.

Count[px][k] = Count[px][k-1] // not using element S[k] 
P pq = f(px,P(S[k])) // property pq of appending element S[k] 
j = index of previous location in string where S[j]==S[k] 
Count[pq][k] += Count[px][k-1] // using element S[k] 
Count[pq][k] -= Count[px][j-1] // Removing double counts