题目

LeetCode.516.最长回文子序列（中等）

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

题解

回文子序列的定义一定要搞清，不然不知道怎么求解。

根据示例，一个回文子序列是要求首尾字符是相同的，中间可以不是回文子串，但是求解序列长度其实是要删除不能构成回文子串的字符，然后再看剩下能构成回文子串的字符数是多少。

那么什么情况下不能构成回文串？
一个字符串首尾字符不相同，一定不是回文串。

那应该删除首尾哪一个字符？
因为要求最长的回文子序列，删除哪个字符后能够得到最长的回文子序列就删除哪个，但是不知道是哪个是最长的，所以都分别删除试一下，然后取最大值。

删除字符后怎么办？
删除字符后剩余字符串判断是不是回文子序列，还是一样的方法，所以可以递归进行。

递归处理
先看字符串两端字符是否相同：

如果相同，可以算作回文子序列了，长度加2，但是总长度多少还得看去除首尾字符后剩余的字符串的回文子序列长度。
如果不相同，删除最左边字符，或者删除最右边字符，再看剩下的字符串的回文子序列长度。

边界
递归一直在缩减字符串。
如果字符串是偶数个字符，每次两个字符的删减，最后肯定只剩两个字符，再缩减，会出现左指针索引大于指针右索引，直接返回0就行。
如果字符串一直一个个的缩减，最后左指针和右指针都会指向一个字符，一个字符是回文子串，长度返回1。

class Solution {
    fun longestPalindromeSubseq(s: String): Int {
        fun longest(i: Int, j: Int): Int {
            if (i == j) return 1
            if (i > j) return 0
            return if (s[i] == s[j]) {
                2 + longest(i + 1, j - 1)
            } else {
                maxOf(
	                // 删除最左边字符
                    longest(i + 1, j),
                    // 删除最右边字符
                    longest(i, j - 1)
                )
            }
        }
        return longest(0, s.length - 1)
    }
}

可以发现递归是存在很多重叠子问题的，因为长的序列要依赖短的序列求解，比较短的序列结果就要反复被递归，这增加了耗时，所以给中间计算过的状态记录一下。

记忆化递归

class Solution {
    fun longestPalindromeSubseq(s: String): Int {
        val n = s.length
        val memo = Array(n) { IntArray(n) { -1 } }
        fun longest(i: Int, j: Int): Int {
`            if (i == j) return 1
            if (i > j) return 0
            if (memo[i][j] > 0) return memo[i][j]
            memo[i][j] = if (s[i] == s[j]) {
                2 + longest(i + 1, j - 1)
            } else {
                maxOf(
                    longest(i + 1, j),
                    longest(i, j - 1)
                )
            }
            return memo[i][j] 
        }
        return longest(0, n - 1)
    }
}

自底向上递推

状态转移方程：
设dp[i][j]为字符串s[i, j]最长回文子序列长度。
s[i] == s[j]时，dp[i][j] = 2 + dp[i + 1][j - 1]
s[i] != s[j]时，dp[i][j] = maxOf(dp[i + 1][j], dp[i][j - 1])

注意递推顺序，i是从i + 1递推来的，所以要从大到小遍历。
j依赖j - 1，所以j是从小到大遍历。

由于s[i, j]要构成字符串，所以i <= j < n。
i == j时，dp[i][j] = 1，可以单独处理。

class Solution {
    fun longestPalindromeSubseq(s: String): Int {
        val n = s.length
        val dp = Array(n) { i -> IntArray(n) { j -> if (i == j) 1 else 0 } }
        for (i in n - 1 downTo 0) {
            for (j in i + 1 until n) {
                dp[i][j] = if (s[i] == s[j]) 2 + dp[i + 1][j - 1]
                else maxOf(dp[i + 1][j], dp[i][j - 1])
            }
        }
        return dp[0][n - 1]
    }
}

时间复杂度O(n^2)
空间复杂度O(n^2)