使用属性动态编程子序列计数？

Question

考虑动态编程问题,该问题询问序列S有多少不同的子序列(不一定是连续的)具有值p0的特定属性P.

P的范围小且有限,并且有一种有效的计算P的方法:

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

其中+表示序列连接.

一种方法是计算S[1] + S[2] + ... + S[k]具有属性px的S 的前缀有多少个子序列.(存放在这里Count[px][k])

所以递归是:

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

然后答案是:

return Count[p0][S.length]

当S的元素成对不同时,这将起作用,但是它会计算两个具有相同值但使用不同位置的不同元素的子序列.

如何修改此算法,使其只计算一次相等的子序列？(即仅计算不同的子序列)

Answer 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