求字元串最長不連續迴文序列的深入研究

給定一個字元串s，你可以從中刪除一些字元，使得剩下的串是一個迴文串。如何刪除才能使得迴文串最長呢？

輸出需要刪除的字元個數。

這個普遍是使用動態規劃，但是都是遍歷全部N*N次不斷累加後取最後一個數字。

我覺得沒有必要全部遍歷，於是研究了一下。

1.我們來看一下，這個字元串按照動態規劃生成的數組：

我們發現，按照動態規劃生成數組，找到的最長迴文序列：「04566540」對應i，j的連線，其實是按照次對角線軸對稱的，那麼是否可以不遍歷全部，只遍歷對角線左上方呢？答案是肯定的！

那麼只需要找出前一半的長度，乘以二不就是我們要的結果了？可是有一個問題啊，讓我們看一下下面的情況：

這種情況如何處理？如果判斷經過對角線就+1？不不不，這個判斷太麻煩，我使用了0.5/0兩個數處理，一會代碼中可以體現出來。

剛剛說到只遍歷一半，那也還是n方啊，沒有什麼實質性的改變。接下來我想到一個新的點子：我發現其實從一個點所在的「層」到對角線的增量的最大值，是一個固定的值！那麼，這個發現有什麼用呢？？還是通過一個圖來看一下：

啊對了，首先要介紹一下這裡「層」的概念，其實很簡單，就是平行於次對角線的線，從左上角往右下方看：第一層就是一個0，第二層是0 0，那麼最後一層就是對角線啦，很顯然每一層上的 i + j 都是相等的。

那麼我們繼續，剛才說到每層到對角線的徑直增量（就是每增加一層，數組的值都加一）最大值我推出的公式：

static float halfMaxLength(int layerIndex){ return (finalLayer - layerIndex + 1) / 2f;}

我們看一下這個公式：假設我們用上圖的第4層（第二行橫著數第一個1，層數從0開始，最後一層對角線就是n-1）舉例，徑直增量最大值是（n-1 - 4 + 1）/ 2 = 3，同時我們也看到第四層+1（就是這個1的左上角的4，其實在動態規劃演算法中是邊界0來的）往右下看第六層+1第8層+1正好是總增量=增量最大值，這說明了什麼呢？這說明了：從第四層的下一層所有節點，即使到對角線的增量達到最大值，也不可能超過第四層的總增量了，那麼我們可以直接判斷：這個就是我們想要的最大值！也就是3 * 2 = 6！

這個是一個比較特殊的例子，那麼通常，一般不會像這樣層層遞增，這個時候又怎樣呢？我們看一下增量最大值和總增量的差值dist=max-total，剛才的例子是dist=0，那麼dist=1呢？當dist=1時，很容易想，當前層的下一層，即使達到最大值，也才能與當前總增量相等！再後面的層就更別說了。那麼dist>1呢？比如dist=3，同樣很容易想到，能夠與當前的總增量抗衡的，只有當前層+3之前的這麼幾層吧？因為+3層，即使達到增量最大值，也才能與當前的總增量相等，後面的層就更不用說了。

總結一下，上面的意思就是說：當dist<=1時，我們可以直接把當前的總增量返回而不用再遍歷之後的節點！當dist>1時，我們只需遍歷當前層+dist層以里的所有節點而不用再遍歷之後的節點！

這樣之後，需要遍歷的節點就少了很多很多了。

那麼，還能不能優化了呢？？

當然可以！

先看下圖：

先不考慮上面所說的層的優化，正常我的演算法遍歷應該是這樣的，按照藍色線條方向遍歷，那麼，我們看到，圖中兩個三角形區域，在三角形頂點處是會發生遞歸的（層與層之間的轉換也是遞歸），加入說我們的藍色線條走到了第一個三角形頂點，發生遞歸，那麼一定涉及到右上方三角形內全部或一部分的節點的遍歷，遞歸返回後，藍色線條繼續前行，那麼我們很容易的看到，藍線又遍歷了好幾次右上方三角形內部的節點！這不科學，這種遍歷完全是無用功！

由此，誕生了一個iRight和一個jBottom（對應於左邊界iLeft和jTop）這兩個東西是啥？有了這兩個東西，就可以對藍色線條進行限制！就可以避免藍色線條第二次進入三角形管內的時候進行多餘的遍歷！

好了，說了這麼多，我們直接上代碼！雖然這個演算法我覺得很不錯，但是畢竟遞歸，我寫的倉促，現在沒太多時間去消除遞歸，留著有時間把遞歸消除，這個演算法應該是很不錯的，最好的情況是 n/2，調用遞歸 n/2 次，最壞n方/2，調用遞歸n+m（m為迴文內字元對應上的次數）次，所以以後我必須要消除遞歸：

import java.util.Scanner;public class Test { static int total = 0 ; public static void main(String[] args){ Scanner s = new Scanner(System.in); while( s.hasNext()){ String str = s.next(); logln( str.length() - find(str) ); } } static int yBottom , xRight , finalLayer; static int find(String str){ if(str.length() <= 1)return 1; xRight = yBottom = finalLayer = str.length() - 1; float res = 2 * findLength(str.toCharArray() , 0 , 0 , -1 , -1 , 0 , str.length() - 1 , 0.5f ); return (int)res; } /** * * @param str 字元串數組 * @param i 當前x坐標 * @param j 當前y坐標 * @param iLeft x坐標左邊界 * @param jTop y坐標上邊界 * @param curValue * @param endLayer 計算所需最後的層 * @param seed 用於補充0.5，因為是只計算一半 * @return */ static float findLength(char[] str, int i, int j, int iLeft , int jTop , float curValue, int endLayer, float seed){ int curLayer = i + j; if( curLayer > endLayer ) return curValue; if( curLayer == endLayer ) return curValue + (str[i] == str[str.length - 1 - j] ? seed : 0); int ii = i , jj = j ; float curLen = 0; while(ii > iLeft ){ if(str[ii] == str[str.length - 1 - jj] && ( jj <= yBottom || ii <= xRight )){ curLen = findLength(str , ii+1 , jj+1 , ii , jj , curValue + 1 , finalLayer , 0.5f); float delta = curLen - curValue; xRight = Math.min( xRight , ii ); yBottom = Math.min( yBottom , jj ); int dist = (int)(halfMaxLength( curLayer ) - delta ) ; if(dist <= 1)break; endLayer = curLayer + dist; } ii--;jj++; } if(ii == iLeft) return Math.max( curLen , findLength( str, i+1 , j , iLeft , jTop , curValue , endLayer , endLayer == finalLayer ? 0.5f : 0) ); else return curLen; } static float halfMaxLength(int layerIndex){ return (finalLayer - layerIndex + 1) / 2f; } static void log(Object...objs){ for(Object obj : objs) System.out.print(obj); } static void logln(Object...objs){ for(Object obj : objs) System.out.println(obj); }}

能力有限，請各路大佬指點

=============================================

消除遞歸心得在另一篇文章里模擬狀態機消除遞歸心得