算法：字元串消除問題的數學證明

問題：

給定一個字元串，僅由A、B、C3個字母組成。當出現連續兩個不同的字母時，你可以用另外一個字母替換它，如有AB或BA連續出現，你把它們替換為字母C；有AC或CA連續出現時，你可以把它們替換為字母B；有BC或CB連續出現時，你可以把它們替換為字母A。可以不斷反複按照這個規則進行替換，目标是使得最終結果所得到的字元串盡可能短，求最終結果的最短長度。

輸入：字元串。長度不超過200，僅由ABC3個字母組成。 輸出：按照上述規則不斷消除替換，所得到的字元串最短的長度。

例如：

輸入CAB，輸出2。因為我們可以把它變為BB或者變為CC。

輸入BCAB，輸出1。我們可以把它變為AAB到AC到B，也可以把它變為BBB，但因為前者長度更短，是以輸出1。

先給出幾個概念

純字元串：隻含有一種字母的字元串稱為純字元串，例如AAA就是一個純字元串

混字元串：含有至少兩種字母的字元串稱為混字元串，例如ABC就是一個混字元串

最優長度：字元串通過消除的最終結果的最短長度，稱為該字元串的最優長度。上面的示例中，CAB的最優長度為2，BCAB的最優長度為1

最優串：字元串通過消除達到最優長度時的字元串稱為最優串，最優串可能不止一個。如CAB的最優串為BB和CC，而BCAB的最優串為B。最優串一定是純字元串

統計向量：用（X，Y，Z）表示字元串的統計向量，其中X、Y、Z分别表示字元串中字母A、B、C的個數。上面的示例中，CAB的統計向量為（1，1，1），BCAB的統計向量為（1，2，1）

統計特征向量：用（X，Y，Z）表示字元串的統計特征向量，其中X、Y、Z分别表示字元串中字母A、B、C的個數的奇偶性，用“奇”、“偶”表示。CAB的統計特征向量為（奇，奇，奇），BCAB的統計特征向量為（奇，偶，奇）

再給出幾個推論

推論1：純字元串的最優長度就是純字元串的長度。

很明顯的，隻有一個字母，沒法消除，是以最優長度就是純字元串的長度

推論2：在純字元串前或後加另一個字母得到新的混字元串，則新混字元串的最優長度為1

例如：BBBBBBBA。則消除的過程是，BBBBBBBA >> BBBBBBC >> BBBBBA >> BBBBC >> BBBA >> BBC >> BA >> C

其他的類似，不再贅述

推論3：若純字元串的長度為偶數，則在前或後添加另一個字母得到新的混字元串，則新混字元串的最優串為添加的字母；若純字元串的長度為奇數，則新混字元串的最優串為剩下的一個字母

假設純字元串為BB，添加字母A，則新混字元串為BBA，BBA >> BC >> A

假設純字元串為BBBB，添加字母A，則新混字元串為BBBBA，BBBBA >> BBA >> A

以此類推，推論3的前半部得證

假設純字元串為B，添加字母A，則新混字元串為BA，BA >> C

假設純字元串為BBB，添加字母A，則新混字元串為BBBA，BBBA >> BA >> C

以此類推，推論3的後半部得證

推論4：混字元串的最優長度不超過2（為1或2）

證明：

首先混字元串通過不停的消除，最終能得到一個純字元串（因為若還有不同的字母，則必相鄰，則還能繼續消除）。

若該純字元串的長度為1或2，則證明了該推論（不過，就算純字元串長度為2，還沒證明最優長度一定是2，可以肯定的是最優長度不超過2，即1或2都有可能）

若該純字元串的長度大于2，不失一般性，假設該純字元串的長度為K（K＞2），該純字元串都由字母B組成（字母A、C是一樣的），該純字元串是通過N（N≥1）步消除得到的

那麼回退一步，第N-1步消除得到的混字元串為B……BACB……B，其中A前面有K1個B，C後面有K2個B，K1+K2=K-1。（也有可能是B……BCAB……B，和B……BACB……B是一緻的，不再贅述了）

那麼，根據K1和K2的取值不同，可以優化出不同的消除

K1是奇數，K2是奇數。利用推論3，可知B……BA >> C；CB……B >> A；B……BACB……B >> CA >> B，最優串是B，最優長度為1

K1是奇數，K2是偶數。利用推論3，可知B……BA >> C；CB……B >> C；B……BACB……B >> CC，則最優長度不超過2（因為還沒法證明最優長度不會是1）

K1是偶數，K2是奇數。利用推論3，可知B……BA >> A；CB……B >> A；B……BACB……B >> AA，則最優長度不超過2（因為還沒法證明最優長度不會是1）

K1是偶數，K2是偶數。利用推論3，可知B……BA >> A；CB……B >> C；B……BACB……B >> AC >> B，最優串是B，最優長度為1

綜上所述，混字元串的最優長度不超過2

推論5：統計特征向量為（奇，奇，奇）或（偶，偶，偶）的混字元串的最優長度為2；其餘的混字元串的最優長度為1

考察一下，每次消除，統計特征向量的變化過程

假設字元串的統計特征向量為（奇，奇，奇）

假設消除是AC（或CA） >> B，則A和C的個數減1，而B的個數增加1，則統計特征向量變為（偶，偶，偶）

假設消除是AB（或BA） >> C，則A和B的個數減1，而C的個數增加1，則統計特征向量變為（偶，偶，偶）

假設消除是BC（或CB） >> A，則B和C的個數減1，而A的個數增加1，則統計特征向量變為（偶，偶，偶）

綜上所述，統計特征向量為（奇，奇，奇）的混字元串，經過1次消除後，統計特征向量變為（偶，偶，偶）

同理可證，統計特征向量為（偶，偶，偶）的混字元串，經過1次消除後，統計特征向量變為（奇，奇，奇）

由此可知，反複消除後，統計特征向量為（奇，奇，奇）的混字元串的最優串的統計特征向量是（偶，偶，偶）。（因為最優串是純字元串，隻能有1種字元，是以最優串不可能是（奇，奇，奇））

同理可證，統計特征向量為（偶，偶，偶）的混字元串的最優串的統計特征向量也是（偶，偶，偶）。

是以，統計特征向量為（奇，奇，奇）或（偶，偶，偶）的混字元串的最優串的統計特征向量為（偶，偶，偶）

假設字元串的統計特征向量為（奇，偶，偶）

假設消除是AC（或CA） >> B，則A和C的個數減1，而B的個數增加1，則統計特征向量變為（偶，奇，奇）

假設消除是AB（或BA） >> C，則A和B的個數減1，而C的個數增加1，則統計特征向量變為（偶，奇，奇）

假設消除是BC（或CB） >> A，則B和C的個數減1，而A的個數增加1，則統計特征向量變為（偶，奇，奇）

綜上所述，統計特征向量為（奇，偶，偶）的混字元串，經過1次消除後，統計特征向量變為（偶，奇，奇）

同理可證，統計特征向量為（偶，奇，奇）的混字元串，經過1次消除後，統計特征向量變為（奇，偶，偶）

由此可知，反複消除後，統計特征向量為（奇，偶，偶）的混字元串的最優串的統計特征向量是（奇，偶，偶）。（因為最優串是純字元串，隻能有1種字元，是以最優串不可能是（偶，奇，奇））

同理可證，統計特征向量為（偶，奇，奇）的混字元串的最優串的統計特征向量也是（奇，偶，偶）。

是以，統計特征向量為（奇，偶，偶）或（偶，奇，奇）的混字元串的最優串的統計特征向量為（奇，偶，偶）

同理可證

統計特征向量為（偶，奇，偶）或（奇，偶，奇）的混字元串的最優串的統計特征向量為（偶，奇，偶）

統計特征向量為（偶，偶，奇）或（奇，奇，偶）的混字元串的最優串的統計特征向量為（偶，偶，奇）

由推論4可知，混字元串的最優長度不超過2

如果，混字元串的最優長度為1，則最優串是A，統計特征向量是（奇，偶，偶）；是B，統計特征向量是（偶，奇，偶）；是C，統計特征向量是（偶，偶，奇）

如果，混字元串的最優長度為2，則最優串是AA或BB或CC，統計特征向量是（偶，偶，偶）

是以，統計特征向量為（奇，奇，奇）或（偶，偶，偶）的混字元串的最優長度是2。

統計特征向量為（奇，偶，偶）或（偶，奇，奇）的混字元串的最優長度為1，最優串是A

統計特征向量為（偶，奇，偶）或（奇，偶，奇）的混字元串的最優長度為1，最優串是B

統計特征向量為（偶，偶，奇）或（奇，奇，偶）的混字元串的最優長度為1，最優串是C

證明完畢

結論：

1、純字元串的最優串就是自身，最優長度就是自身的長度

2、統計特征向量為（奇，奇，奇）或（偶，偶，偶）的混字元串的最優長度為2

3、其餘的混字元串的最優長度是1，其中統計特征向量為（奇，偶，偶）或（偶，奇，奇）的混字元串的最優串是A；統計特征向量為（偶，奇，偶）或（奇，偶，奇）的混字元串的最優串是B；統計特征向量為（偶，偶，奇）或（奇，奇，偶）的混字元串的最優串是C

    本文轉自萬倉一黍部落格園部落格，原文連結：http://www.cnblogs.com/grenet/p/3300591.html，如需轉載請自行聯系原作者