Leetcode 730

Leetcode 730 Count Distinct Palindrome Subsequences

题目大意： 求对称回文子序列的个数

代码：https://www.cnblogs.com/fenice/p/7979770.html

const int mod=1e9+7;
class Solution {
public:
    int dfs(int l,int r,int k,string& S,vector<vector<vector<int> > >& dp) {
        if(r<l) return 0;
        if(l==r) return (k==S[l]-'a')?1:0;
        if(dp[l][r][k]>=0) return dp[l][r][k];
        int& res=dp[l][r][k]=0;
        if(r-l==1) {
            if(S[l]==S[r]&&k==S[l]-'a') return res=2;
            if(k==S[l]-'a'||k==S[r]-'a') return res=1;
            return res=0;
        }
        if(S[l]==S[r]&&S[l]-'a'==k) {
            res=2;
            for(int i=0; i<4; i++) {
                res+=dfs(l+1,r-1,i,S,dp);
                res%=mod;
            }
        } else {
            if(S[l]-'a'==k){
                res=dfs(l,r-1,k,S,dp);
            }else{
                res=dfs(l+1,r,k,S,dp);
            }
        }
        return res;
    }

    int countPalindromicSubsequences(string S) {
        int n=S.length();
        vector<vector<vector<int> > > dp(n,vector<vector<int> >(n,vector<int>(4,-1)));

        int ans=0;
        for(int i=0; i<4; i++) {
            ans+=dfs(0,n-1,i,S,dp);
            // cout<<ans<<endl;
            ans%=mod;
        }

        return ans;

    }
};