Design an algorithm to find the longest palindrome(回文) subsequence for a given string S. A subsequence is a sequence that can be derived from a string by deleting some chars without changing the order of the remaining ones. A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. For example, one longest palindrome subsequence of string “DABBEAF” is “ABBA”, whose length is 4. ( NOTICE: You’re NOT allowed to use the algorithm for Longest Common Subsequence problem! )

可以使用动态规划思想来解决这个问题。

首先，我们定义一个二维数组dp，dp[i][j]表示从i到j的子串中最长的回文子序列长度。

接下来，我们考虑如何填充这个二维数组。对于dp[i][j]，如果s[i] == s[j]，那么dp[i][j] = dp[i+1][j-1] + 2，因为s[i]和s[j]可以作为回文子序列的两个端点，并且中间的子串也一定是回文的。如果s[i] != s[j]，那么dp[i][j] = max(dp[i+1][j], dp[i][j-1])，因为s[i]和s[j]不可能同时作为回文子序列的端点，所以我们需要在i+1到j和i到j-1两个子串中选择一个最长的回文子序列。

最后，dp[0][n-1]就是整个字符串的最长回文子序列长度。

下面是Python代码实现：

def longest_palindrome_subsequence(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for i in range(n-1, -1, -1):
        for j in range(i+1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][n-1]

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