一个串的最长回文子序列的长度

题目描述：给定一个字符串str，返回这个字符串的最长回文子序列的长度，比如 str="a12b3c43def2ghi1kpm"，最长回文子序列是”1234321" 或者"123c321"，返回长度7。

way：转化为求原串和逆序串的最长公共子序列。

way2：f函数，计算str从L到R上的最长回文子序列的长度。要L不要R，要R不要L，要L要R，不要L不要R。终止条件。

//返回str[L...R]的最长回文子序列长度
int f(string s, int L, int R)
{
	if(L==R) return 1;
	if(L==R-1)
	{
		return s[L]==s[R]?2:1;
	}
	//要L不要R
	int p1=f(s, L, R-1);
	//要R不要L
	int p2=f(s, L+1, R);
	//不要L不要R
	int p3=f(s, L+1, R-1);
	//要L要R
	int p4=f(s, L+1, R-1) +s[L]==s[R]?2:0;
	return max(p1,max(p2,max(p3,p4)));
}
 
int way(string s)
{
	int n=s.size();
	return f(s, 0, n-1);
}

way3：改dp。一定要画图看。

//改dp
int way2(string s)
{
	int n=s.size();
	if(n==0) return 0;
	vector<vector<int>>dp(n, vector<int>(n,0));
	dp[n-1][n-1]=1;
	for(int i=0; i<=n-2; i++)
	{
		dp[i][i]=1;
		dp[i][i+1]=s[i]==s[i+1]?2:1;
	}
	//L从大往小,R从小往大,画图将dp[i][i],dp[i][i+1]填掉也知道L从n-3开始
	for(int L=n-3; L>=0; L--)
	{
		for(int R=L+2; R<n; R++)
		{
			int p1=dp[L][R-1];
			int p2=dp[L+1][R];
			int p3=dp[L+1][R-1]+s[L]==s[R]?2:0;
			dp[L][R]=max(p1,max(p2,p3));
		}
	}
	return dp[0][n-1];
}