最长回文子序列

题目描述：

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

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

示例 1：

输入：s = “bbbab”
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。
示例 2：

输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。

提示：

1 <= s.length <= 1000
s 仅由小写英文字母组成

思路:

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

动态规划做，[i,j]是从i到j位的最大回文数。

代码:

func longestPalindromeSubseq(s string) int {
    n := len(s)
    dp := make([][]int, n+1)
    for i:=0;i<=n;i++{
        dp[i] = make([]int, n+1)
        dp[i][i] = 1
    }
    for L :=2;L<=n;L++{
        for i:=0;i<n;i++{
            j := i+L -1
            if j>=n{
                continue
            }
            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])
            }
        }
    }
    //fmt.Println(dp)
    return dp[0][n-1]
}

代码效率：

执行用时：28 ms, 在所有 Go 提交中击败了58.88%的用户
内存消耗：17 MB, 在所有 Go 提交中击败了75.61%的用户