最长回文子串、最长回文子序列、回文子序列个数

1.最长回文子序列

要求：

给定字符串，求它的最长回文子序列长度。回文子序列反转字符顺序后仍然与原序列相同。例如字符串abcdfcba中，最长回文子序列长度为7，abcdcba或abcfcba。

思路：

动态规划思想

对于任意字符串，如果头尾字符相同，那么字符串的最长子序列等于去掉首尾的字符串的最长子序列加上首尾；如果首尾字符不同，则最长子序列等于去掉头的字符串的最长子序列和去掉尾的字符串的最长子序列的较大者。

因此动态规划的状态转移方程为：

（i<=j），则：

状态初始条件：dp[i][i]=1 （i=0：n-1）

状态转移方程：dp[i][j]=dp[i+1][j-1] + 2  if（str[i]==str[j]）

                   dp[i][j]=max(dp[i+1][j],dp[i][j-1])  if （str[i]!=str[j]）

计算dp[i][j]时需要计算dp[i+1][*]或dp[*][j-1]，因此i应该从大到小，即递减；j应该从小到大，即递增。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

int longestPalindromeSubSequence(string s){
  int len = s.size();

  vector<vector<int> >dp(len, vector<int>(len));

  for (int i = len - 1; i >= 0; i--){
    dp[i][i] = 1;
    for (int j = i + 1; j <= len - 1; j++){
      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][len - 1];
}

int main(){

  string s = "abccba";

  cout << longestPalindromeSubSequence(s) << endl;

  return 0;
}

二、回文子序列个数

动态规划思想

字符串的回文子序列个数就等于去掉头的字符串的回文子序列个数+去掉尾的字符串的回文子序列个数-去掉头尾的字符串的回文子序列个数；如果头尾字符相等，那么除了上述的子序列个数之外，还要加上首尾相等时新增的子序列个数，1+去掉头尾的字符串的回文子序列个数，1指的是加上头尾组成的回文子序列，如aa，bb等。

因此动态规划的状态转移方程为：

（i<=j），则：

状态初始条件：dp[i][i]=1 （i=0：n-1）

状态转移方程：dp[i][j]=dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]  if（str[i]！=str[j]）

                   dp[i][j]=dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]+dp[i+1][j-1]+1=dp[i+1][j] + dp[i][j-1]+1  if （str[i]==str[j]）

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

int NumOfPalindromeSubSequence(string s){
  int len = s.size();

  vector<vector<int> >dp(len, vector<int>(len));

  for (int i = len - 1; i >= 0; i--){
    dp[i][i] = 1;
    for (int j = i + 1; j <= len - 1; j++){
      dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
      if (s[i] == s[j]){
        dp[i][j] += 1 + dp[i + 1][j - 1];
      }
    }
  }
  return dp[0][len - 1];
}

int main(){

  string s = "abccba";
  cout << NumOfPalindromeSubSequence("abcbaddabcba") << endl;

  return 0;
}