Title source

• leetcode：730. Count how many different palindrome subsequences can be generated

Title Description

class Solution {
    
public:
    int countPalindromicSubsequences(string s) {
    

    }
};

title

Similar topics ： leetcode：940. How many subsequences with different literals

Recurrence of violence

There are two choices for each character: Yes and no , Finally, judge whether it is a palindrome string

class Solution {
    
    bool isP(string path, int pi){
    
        if(pi == 0){
    
            return false;
        }
        
        int L = 0, R = pi - 1;
        while (L < R) {
    
            if (path[L++] != path[R--]) {
    
                return false;
            }
        }
        return true;
    }
    int process(string s, int si, string path, int pi){
    
        if(si == s.length()){
    
            return isP(path, pi) ? 1 : 0;
        }
        
        int ans = process(s, si + 1, path, pi);
        path[pi] = s[si];
        ans += process(s, si + 1, path, pi + 1);
        return ans;
    }
public:
    int countPalindromicSubsequences(string s) {
    
        if(s.empty()){
    
            return 0;
        }
        string path;
        return process(s, 0, path, 0);
    }
};

Dynamic programming

For palindromes , Basically, they try to model in scope

therefore , We define dp[i][j] Express ：

• from $str[i....j]$ How many palindromes can be found in all subsequences of , Empty string does not count
• that ： The final $dp[0][N-1]$ That's what we want

Try on the scope , Often go to the beginning of the discussion 、 How to divide the possibilities at the end . There are four possibilities ：

• Palindrome subsequence A certain No choice $str[i]$, A certain No choice $str[j]$
• Palindrome subsequence A certain No choice $str[i]$, A certain choice $str[j]$
• Palindrome subsequence A certain choice $str[i]$, A certain No choice $str[j]$
• Palindrome subsequence A certain choice $str[i]$, A certain choice $str[j]$

Final $dp[i][j]=a+b+c+d$

We can treat a long string as a short string plus two characters around , So there is s[i,j] = s[i] + s [i+1,j-1] + s[j], such as ： Such as ：“bccb” Can be seen as “cc" Add "b”, At this point, let's discuss it according to the situation

(1) If s[i] == s[j], Equivalent to we give s[i + 1, j - 1] Add two identical characters to the left and right , Then we calculate the number of different palindrome sequences

• ① $s[i+1,j-1]$ There are no characters and s[i] equal

  • Set the string "bcb", be "bcb" The palindrome subsequence of is ：c、bcb 、b、bb（ b、c、bb、bcb ）
  • Set the string "abcba", be ：
    • It is equivalent to giving "bcb" A new palindrome subsequence can be formed by adding a character to the left and right of the subsequence of ,
    • Plus "a"( The character itself is a palindrome subsequence ) and "aa"( Palindrome subsequence of two identical characters )
    • So at this time $dp[i][j]=2dp[i+1][j-1]+2$（ Of itself 4 individual + A new generation of 4 individual +2 Separately generated ）
      

• ②$s[i+1,j-1]$ There is a character and s[i] equal

  • Set the string "bcb", be "bcb" The palindrome subsequence of is ： b、c、bb、bcb
  • Set the string "cbcbc", Then the palindrome subsequence is ：b、c、bb、bcb、cbc、ccc、cbbc、cbcbc、c、 cc
  • Suppose one character is equal , The palindrome subsequence of this single character has been recorded before ( Only... Can be added "cc", Cannot add "c")
  • So at this time $dp[i][j]=2dp[i+1][j-1]+1$（ Of itself 4 individual + A new generation of 4 individual +1 Separately generated ）

• ③$s[i+1,j-1]$ There are two or more characters and s[i] equal

  • If there are two or more characters , Then we need to find its location , And delete the palindrome subsequence of repeated calculation , And two separate ones have been calculated before .
  • Assuming a string "dabcbad", We add characters to both sides "a"
  • Then "a" The characters will match the middle "bcb" Form repeated palindrome subsequences , Because there have been "a" and "bcb" Form palindrome subsequence

(2) if s[i] != s[j], Then we add s[i] and s[j] Can not form palindrome subsequence , It can only be calculated separately

• for instance
  • Calculation abb The palindrome subsequence of ：a、b、bb
    • Calculation ab The palindrome subsequence of ：a、b
    • Calculation bb The palindrome subsequence of ：b、bb
  • Look at it , You can find s[L+1][R-1] It was calculated repeatedly

in summary , The equation of state transfer is ：

class Solution {
    
public:
    int countPalindromicSubsequences(string S) {
    
        int strSize = S.size(), M = 1e9 + 7;
        //dp[i][j] It means S[i, j] The number of different palindrome subsequences in this string 
        vector<vector<int>> dp(strSize, vector<int>(strSize, 0));
        // initialization , A string of length is also a result 
        for (int i = 0; i < strSize; ++i) {
    
            dp[i][i] = 1;
        }
        // Start dynamic planning 
        for (int i = strSize - 2; i >= 0; --i){
    
            for (int j = i + 1; j < strSize; ++j){
    
                // The upper two floors for Loops are used to enumerate intervals [i, j],i Used to determine the starting point of the interval ,j Determine the end of the interval , And the length of the interval is determined by 2 Gradually increase 
                if (S[i] == S[j]) {
    
                    //left Used to find and S[i] The first subscript at the same left end ,right Used to find and S[i] The first subscript at the same right end 
                    int left = i + 1, right = j - 1;
                    while (left <= right && S[left] != S[i]) {
    
                        ++left;
                    }
                    while (left <= right && S[right] != S[i]) {
    
                        --right;
                    }
                    if (left > right) {
    
                        // There is no and S[i] Same letter , for example "aba" This situation 
                        // among dp[i + 1][j - 1] Is the number of palindrome subsequences in the middle part , Because all subsequences in the middle can exist alone , You can also wrap letters on the outside a, So it's in pairs , To ride 2.
                        // Add 2 The reason is the outer "a" and "aa" It should also be statistically 
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
                    } 
                    else if (left == right) {
    
                        // There is only one and S[i] Same letter , Namely "aaa" This situation ,
                        // Multiply by 2 Part of the reason is the same as the above ,
                        // Add 1 The reason is a single letter "a" The situation of has been calculated in the middle part , The outer layer can only be added "aa" 了 .
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
                    } 
                    else {
    
                        // There are at least two and S[i] Same letter , Namely "aabaa" This situation ,
                        // Multiply by 2 Part of the reason is the same as the above , To subtract left and right The reason for the number of subsequences in the middle part is that it has been calculated twice , Reduce the extra .
                        dp[i][j] = dp[i + 1][j - 1] * 2 - dp[left + 1][right - 1];
                    }
                } 
                else {
    
                    //dp[i][j - 1] + dp[i + 1][j] Here we calculate dp[i + 1][j - 1] Two times 
                    dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
                }
                dp[i][j] = (dp[i][j] < 0) ? dp[i][j] + M : dp[i][j] % M;
            }
        }
        return dp[0][strSize - 1];
    }
};