本文共 758 字，大约阅读时间需要 2 分钟。

1. 题目

给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。

示例 1:输入:"bbbab"输出:4一个可能的最长回文子序列为 "bbbb"。示例 2:输入:"cbbd"输出:2一个可能的最长回文子序列为 "bb"。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-palindromic-subsequence

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：

注意，子序列，可以隔着字符

class Solution {
   public:    int longestPalindromeSubseq(string s) {
       	int i, j, n = s.size();    	vector
   
    
     > dp(n,vector
     
      (n,0));        for(i = 0; i < n; ++i)            dp[i][i] = 1;    	for(j = 0; j < n; ++j)    	{
       		for(i = j-1; i >= 0; --i)//区间从小往大，所以逆序    		{
       			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];    }};
     
    
   

176 ms 67.1 MB