गतिशील प्रोग्रामिंग संपत्ति के साथ परिणामों की गणना?

Question

एक गतिशील प्रोग्रामिंग समस्या पर विचार करें जो पूछता है कि अनुक्रम एस के कितने अलग अनुक्रम (आवश्यक रूप से संगत नहीं) में मूल्य पी 0 की एक निश्चित संपत्ति पी है।

पी की सीमा छोटे और परिमित है, और वहाँ की गणना पी के एक प्रभावशाली तरीका है:

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

जहां + को दर्शाता है अनुक्रम संयोजन।

ऐसा करने का एक तरीका यह होगा कि संपत्ति के पीएक्स वाले S[1] + S[2] + ... + S[k] के उपसर्ग के कितने बाद हैं। (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

मान लीजिए कि अनुक्रम वर्णों का है और एस [के] अक्षर x है।

समस्या यह है कि आपने उन सभी अनुक्रमों को दोहराया है जो एस [के] का उपयोग नहीं करते हैं, लेकिन फिर भी एक्स के साथ समाप्त होते हैं (यह तब हो सकता है जब एक्स अनुक्रम में पहले हुआ हो)।

मान लीजिए कि अंतिम बार एक्स दिखाई देने वाला तत्व एस [जे] था। एक्स के साथ समाप्त होने वाले सभी विशिष्ट अनुक्रमों को केवल जे -1 के लिए सभी विशिष्ट अनुक्रमों की गणना करके और फिर इन सभी पर एक्स जोड़कर दिया जाता है।

इसलिए हम इस गिनती को घटाकर डबल गिनती के लिए सही कर सकते हैं।

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