Динамическое программирование подсчета подследующих свойств?

Question

Рассмотрим проблему динамического программирования, которая задает, сколько четких подпоследовательностей (не обязательно смежных) последовательности S имеет некоторое свойство P значения p0.

Диапазон P мал и конечен, и есть эффективный способ вычисления P:

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

где + обозначает последовательность конкатенацию.

Одним из способов сделать это было бы подсчет количества подпоследовательностей префикса S[1] + S[2] + ... + S[k] из S, обладающих свойством 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 попарно различны, однако он будет считать дважды подпоследовательности, которые имеют равное значение, но используют разные элементы разных позиций.

Как изменить этот алгоритм так, чтобы он считал равные подпоследовательности ровно один раз? (т. е. только отличные подпоследовательности)

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