Geek asks and answers

Dynamic programming of the calculation of the following properties?

Consider a dynamic programming problem that defines how many clear subsequences (not necessarily adjacent) of a sequence S have some property P of value p0.

The range of P is small and finite, and there is an efficient way to calculate P:

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

where +denotes the concatenation of the sequence.

One way to do this is to calculate how many subsequences the prefix S[1] + S[2] + ... + S[k]of S has in the px property. (Save it in Count[px][k])

So recursion is this:

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])

and the answer will be as follows:

return Count[p0][S.length]

This works when the elements of S are pairwise distinct, however he will count two subsequences that are of equal value but use different elements of different positions.

, ? (.. )

+5
1

, S [k] - x.

, , S [k], x ( , x ).

, x S [j]. , x, j-1, x .

, .

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
+2

More articles:


All Articles