迴文的定義，便是從頭或是尾念，都是相同的句子，例如說有名的”上海自來水來自海上”，便是回文的一種．

我們今天的題目就是要在一個字串中找到其最長的迴文子序列長度．注意我們前面提過，子序列是可以中斷的，這就讓題目的難度提高許多

舉例來說: input =”aecda”，演算法返回3，因為最長的迴文子序列是”aca”，長度為3

思考過程

這個問題我們對dp陣列的定義如下

在子字串s[i..j]中，最長迴文子序列的長度為dp[i][j]

為什麼會挑這樣的定義呢，這是因為這個定義比較容易歸納，可以使用已知結果導出未知部分

具體來說，假設已經知道子問題dp[i+1][j-1]的答案(這邊的前項是來自s[i+1..j-1])是否能得到dp[i][j]的值呢？(來自s[i..j]的最長迴文子序列)

假設提供的字串是 ?bwaby? ， 問號代表未知字元，i，j分別是從頭跟尾巴開始的雙指標
則s[i+1..j-1] = bwaby
則dp[i+1][j-1] = 3 (來自bab)
求 s[i..j]的最長迴文子序列長度，也就是dp[i][j]

可以的，取決於那兩個問號所代表的字元，有以下幾種情況

1.兩個字元相等

那很簡單，在原本的dp[i+1][j-1]答案加上2，就是s[i..j]的最長迴文子序列長度

2.兩個字元不相等

代表這兩個字元，不可能一起存在s[i..j]的最長迴文子序列中，那麽我們將這兩個字元分別串連到s[i+1..j-1]之中，看看哪個子字串產生的迴文子序列更長即可

把這兩種情況寫成程式碼

if(s[i]==s[j]){
     dp[i][j] = dp[i+1][j-1] +2
}else{
     dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1])
}

這樣就有狀態轉移方程式了，根據提議，要求的就是dp[0][n-1]的值

實作

先確認基本狀態，i ,j 分別是來自頭尾的指標

1.當i 跟j 相等，代表子字串只有一個字元，那麼最長的迴文子序列就是這個字元，長度為1，填入

2.i 是來自頭的指標，只會小於或是等於j，所以所有的 i > j 都填入0

另外，根據狀態轉移方程dp[i][j]的答案只需要dp[i+1][j-1]，dp[i+1][j]，dp[i][j-1]三種情況就可以了

dp 陣列可以先填入這些

為了保證計算dp[i][j]時，已經先計算完dp[i+1][j-1]，dp[i+1][j]，dp[i][j-1]三種情況，因此我們尋訪的順序也有特別設計，可以斜向或是反向

這邊我們選擇使用反向巡訪來實作，程式碼如下

fun longestPalindromeSub(s:String):Int{
    val n = s.length
    val dp: Array<Array<Int>> = Array(n) { Array(n) { 0 } }
    // fill base case
    for(i in 0 until n){//相同的i j 都是預設為1
        dp[i][i] = 1
    }

    //反向巡訪確保過程中不會缺少某個狀態
    for(i in n-2 downTo 0 ){
        for(j in i+1 until  n){
            if(s[i] == s[j]){
                dp[i][j] = dp[i+1][j-1]+2
            }else{
                dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1])
            }
        }
    }

    return dp[0][n-1]
}