動态規劃之最長回文子串

問題：給出一個字元串S，求S的最長回文子串的長度。

結果：字元串"PATZJUJZTACCBCC"的最長回文子串為"ATZJUJZTA",長度為9。

暴力解法

枚舉子串的兩個端點i和j,判斷在[i, j]區間内的子串是否回文。從複雜度上來看，枚舉端點需要0(n2),判斷回文需要0(n)，是以總複雜度是O(n3)。

動态規劃解決

        令dp[i][j]表示S[i]至S[j]所表示的子串是否是回文子串，是則為1，不是為0。這樣根據S[i]是否等于S[j]，可以把轉移情況分為兩類：

         ①若S[i]=S[j],那麼隻要S[i+1]和S[j-1]是回文子串，S[i]至S[j]就是回文子串；如果S[i+1]至S[j-1]不是回文子串，則S[i]至S[j]一定不是回文子串。

         ②若S[i]!=S[j]，那S[i]至S[j]一定不是回文子串。

由此可以寫出狀态轉移方程

邊界dp[i][i]=1,dp[i][i+1]=(S[i]==S[i+1])?1:0 。

到這裡還有一個問題沒有解決,那就是如果按照i和j從小到大的順序來枚舉子串的兩個端點,然後更新dp[i]lj],會無法保證dp[i + 1][j - 1]已經被計算過,進而無法得到正确的dp[i][i]。

         如圖11-4所示，先固定i=0,然後枚舉j從2開始。當求解dp[0][2]時，将會轉換為dp[1][1],而dp[1][1]是在初始化中得到的;當求解dp[0][3]時,将會轉換為dp[1][2], 而dp[1][2]也是在初始化中得到的;當求解dp[0][4]時，将會轉換為dp[1][3], 但是dp[1][3]并不是已經計算過的值，是以無法狀态轉移。事實上，無論對i和j的枚舉順序做何調整，都無法調和這個沖突，是以必須想辦法尋找新的枚舉方式。

        根據遞推寫法從邊界出發的原理，注意到邊界表示的是長度為1和2的子串，且每次轉移時都對子串的長度減了1,是以不妨考慮按子串的長度和子串的初始位置進行枚舉，即第一遍将長度為3的子串的dp值全部求出，第二遍通過第一遍結果計算出長度為4的子串的dp值…這樣就可以避免狀态無法轉移的問題。如圖11-5所示，可以先枚舉子串長度L (注意: L是可以取到整個字元串的長度S.len()的)，再枚舉左端點i,這樣右端點i+ L- 1也可以直接得到。

public class Solution {

  public static void main(String[] args) {
    maxSubMirrorString("PATZJUJZTACCBCC");
  }

  public static void maxSubMirrorString(String str) {
    char[] chars = str.toCharArray();
    int length = chars.length;
    int dp[][] = new int[length][length];
    int maxSubMirrorStrLength = 1;

    //初始化dp[i][i],dp[i][i+1]
    for (int i = 0; i < length; i++) {
      dp[i][i] = 1;
      if (i < length - 1) {
        if (chars[i] == chars[i + 1]) {
          dp[i][i + 1] = 1;
          maxSubMirrorStrLength = 2;
        }
      }
    }

    //狀态轉移方程
    for (int L = 3; L <= length; L++) {//枚舉子串長度
      //枚舉子串起始端點 起始端點加上子串長度(子串長度包括他本身，是以要-1）必須小于總長
      int j;//子串右端點
      for (int i = 0; (j = i + L - 1) < length; i++) {
        if (chars[i] == chars[j] && dp[i + 1][j - 1] == 1) {
          dp[i][j] = 1;
          maxSubMirrorStrLength = L;//更新最長回文子串長度;
        }
      }
    }

    System.out.println("最長回文子串長度：" + maxSubMirrorStrLength);
  }
}