6

考虑一个动态规划问题，该问题询问序列 S 中有多少不同的子序列（不一定是连续的）具有值 p0 的特定属性 P。

P 的范围小且有限，有一种有效的 P 计算方法：

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

其中+表示序列连接。

一种方法是计算 S 的前缀有多少S[1] + S[2] + ... + S[k]具有属性 px 的子序列。（将其存储在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 的元素成对不同时有效，但是它将计算两次具有相同值但使用不同位置的不同元素的子序列。

我怎样才能修改这个算法，使它只计算相等的子序列一次？（即只计算不同的子序列）

4

1 回答 1

3

假设序列是字符，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
于 2012-08-01T18:59:32.417 回答