730. 统计不同回文子序列 - 力扣LeetCodeProblem:730. 统计不同回文子序列给你一个字符串 s 返回 s 中不同的非空回文子序列个数 。返回对 1e9 7 取余 的结果。思路回文序列去掉首位仍然是一个回文子序列因此想到区间dp定义dp[ i ][ j ]表示下标i...j的非空回文子序列个数接下来是求状态转移方程1.当s[ i ] !s[ j ]时s[i...j]axb其中a s[ i ]b s[ j ]由容斥原理得dp[ i ][ j ] dp[ i1 ][ j ]dp[ i ][ j-1 ]-dp[i1][j-1] 。2.当s[i] s[j]时s[i..j]cxccs[i]s[j]此时有{ccc}如果首尾没有参与回文子序列的数量是dp[i1][j-1]如果首位其中之一参与回文子序列可知一定是c---y--c的形式其中y也是回文串并且属于[i1...j-1]等价于使用了首尾元素数量还是dp[i1][j-1]此时得到的总数是tot2*dp[i1][j-1]在得到的回文串集合中包含3种形式{ccc}{cxcx}统计重复的元素形式为c___c当i1...j-1中存在一个c时tot包含1个重复c当i1...j-1中存在2个及以上c时2个c之间的回文子序列加上2边的c会造成重复因此选择最远的2个c的位置删除之间所有的回文子序列x此外还要删除c和cc。一、s[i]!s[j]二、s[i]s[j]设//i 和 j中间没有出现 c//中间出现一个c//中间出现2个c且2个c相邻//中间出现2个c且2个c不相邻l表示i位置之后c第一次出现位置r表示j之前c最后一次出现位置复杂度时间复杂度: O(n2) O(n^2) O(n2)空间复杂度: O(n2)O(n^2)O(n2)CodeCconst int mod1e97; using ll long long; class Solution { public: int countPalindromicSubsequences(string s) { int ns.size(); vectorvectorlldp(n,vectorll(n)); vectorvectorintpre(n1,vectorint(26,-1)),suf(n1,vectorint(26,n)); for(int i0;in;i){ for(int j0;j26;j){ if(s[i]-aj)pre[i][j]i; else if(i0)pre[i][j]pre[i-1][j]; } } for(int in-1;i0;i--){ for(int j0;j26;j){ if(s[i]-aj)suf[i][j]i; else if(in-1)suf[i][j]suf[i1][j]; } } for(int in-1;i0;i--){ dp[i][i]1; for(int ji1;jn;j){ if(s[i]!s[j])dp[i][j]((dp[i1][j]dp[i][j-1]-dp[i1][j-1])%modmod)%mod; else{ int lsuf[i1][s[i]-a],rpre[j-1][s[j]-a]; if(lr) if(l1r-1) dp[i][j]((2*dp[i1][j-1]-dp[l1][r-1])%modmod)%mod; else{ dp[i][j]2*dp[i1][j-1]%mod; } } else if(lr)dp[i][j](12*dp[i1][j-1]%mod)%mod; else dp[i][j](22*dp[i1][j-1]%mod)%mod; } } } return dp[0][n-1]; } };
