本文共 1102 字，大约阅读时间需要 3 分钟。
原文地址：
在已知的字符串中查找有多少个回文的子序列（没必要对相同的做区分）。注意空字符串不能看作是回文。
例子：
输入 : str = "abcd"输出 : 4解释 :- 回文子序列有 : "a" ,"b", "c" ,"d" 输入 : str = "aab"输出 : 4解释 :- 回文子序列有 :"a", "a", "b", "aa"输入 : str = "aaaa"输出 : 15
以上问题可以做递归定义。
初始化 : i= 0, j= n-1;CountPS(i,j)// 一个字符串中每个单一的字符都是回文的子序列if i == j return 1 // 回文的长度是1// 如果首位字符相同, 那么我们就认为它是一个回文子序列， 并检查剩下的序列(i+1, j), (i, j-1)Else if (str[i] == str[j)] return countPS(i+1, j) + countPS(i, j-1) + 1;else // 当计算countPS(i+1, j) + countPS(i,j-1)的时候，检查剩下的子序列并移除一般的回文子序列因为它们计算了两次 return countPS(i+1, j) + countPS(i, j-1) - countPS(i+1, j-1)
如果我们画一下以上递归方法的递归树，我们可以看到有重复的子问题。因为问题有重复子问题，那么我们就可以用动态规划来解决它。下面是基于动态规划的实现：
// Counts Palindromic Subsequence in a given String#include#include using namespace std;// Function return the total palindromic subsequenceint countPS(string str){ int N = str.length(); // create a 2D array to store the count of palindromic // subsequence int cps[N+1][N+1]; memset(cps, 0 ,sizeof(cps)); // palindromic subsequence of length 1 for (int i=0; i
输出：
Total palindromic subsequence are : 6
时间复杂度：O( N2 )
转载地址：http://ezhii.baihongyu.com/