給定一個字符串，僅由a,b,c 3種小寫字母組成。當出現連續兩個不同的字母時，你可以用另外一個字母替換它，如: 有ab或ba連續出現，你把它們替換為字母c 有ac或ca連續出現時，你可以把它們替換為字母b 有bc或cb 連續出現時，你可以把它們替換為字母a。 你可以不斷反復按照這個規則進行替換，你的目標是使得最終結果所得到的字符串盡可能短，求最終結果的最短長度。 輸入：字符串。長度不超過200，僅由abc三種小寫字母組成。 輸出： 按照上述規則不斷消除替換，所得到的字符串最短的長度。 例如： 輸入cab，輸出2。 因為我們可以把它變為bb或者變為cc 輸入bcab，輸出1。 盡管我們可以把它變為aab -> ac -> b， 也可以把它變為bbb，但因為前者長度更短，所以輸出1。 一看這個題就是一個需要求最優解的問題，考慮使用動態規劃算法， 從字符串的最開始開始搜索，發現第一個不相同的字符，記下位置 從這個位置開始，先把他和他後面的合並，產生一個新字符串 然後把他後面的和他後面的後面合並，產生第二個新字符串 比較這兩個字符串連續一樣的字符數量，取小的那個 接著遞推這個算法，直到所有的字符都一樣為止。 打個比方，題目中所說的bcab。 發現第一個不相同的字符，記下位置，位置為0，因為第0個和第1個就不一樣。 把他和他後面的合並，產生一個新字符串 bc合並，字符串變成 aab 把他後面的和他後面的後面合並，產生第二個新字符串 , ca合並，變成 bbb aab和bbb比較，第一個只有兩個連續相同的，第二個有三個連續相同的，捨棄第二個，取第一個 把aab接著按算法進行計算。 編程的時候稍微注意一下字符串的結尾，別溢出去了。 算法比較簡單，就寫個主要函數吧，github上有全部的。
int _minLength(string s)
{
cout <<"String :" << s << endl;
//判斷是不是所有字符都一樣，如果一樣，算法結束
if(countSameChars(s)==s.length())
return s.length();
//替換第一個子串
string ss1=change(s,1);
//替換第二個子串
string ss2=change(s,2);
//比較兩個新串，取相同字符少的，繼續該算法
if(countSameChars(ss1) <= countSameChars(ss2))
return _minLength(ss1);
else
return _minLength(ss2);
}
<pre></pre> <pre></pre>
