516. 最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。
代码：
class Solution { public: int longestPalindromeSubseq(string s) { // dp[i][j]:表示第i个字符到第j个字符之间，最长的回文子序列长度 int dp[1005][1005]; int l=s.length(); memset(dp,0,sizeof(dp)); for(int i=0;i<l;i++) dp[i][i]=1; for(int i=l-1;i>=0;i--) // for(int i=0;i<l;i++) 因为看递推公式，需要借助下层结果，所以反着循环 for(int j=i+1;j<l;j++) { if(i+1==j) { if(s[i]==s[j]) dp[i][j]=2; else dp[i][j]=1; continue; } if (s[i]==s[j]) {dp[i][j]=dp[i+1][j-1]+2; continue;} if (s[i]!=s[j]) {dp[i][j]=max(dp[i+1][j],dp[i][j-1]); continue;} } return dp[0][l-1]; } };