'''
给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。
示例 1:
输入:
"bbbab"
输出:
4
一个可能的最长回文子序列为 "bbbb"。
示例 2:
输入:
"cbbd"
输出:
2
一个可能的最长回文子序列为 "bb"。
'''

'''
思路：
动态规划四要素
1.状态
dp[i][j]表示s的i个字符到第j个字符组成的子串中，最长的回文序列长度是多少
2.转移方程
如果s的第i个字符和第j个字符相同的话
dp[i][j]=dp[i+1][j-1]
如果s的第i个字符和第j个字符不同的话
dp[i][j]=max(dp[i+1][j],dp[i][j+1])
然后注意遍历顺序，i从最后一个字符开始遍历，j从i+1开始往后遍历，这样可以保证每个子问题都已经算好了
3.初始化
dp[i][j]=1单个字符的最长回文序列是1
4.结果
dp[0][n-1]
'''
def longestPalind(s):
    n=len(s)
    dp=[[0]*n for _ in range(n)]
    for i in range(n-1,-1,-1):
        dp[i][i]=1
        for j in range(i+1,n,1):
            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]
