Leetcode 730. Count Different Palindromic Subsequences

【Leetcode730】Count Different Palindromic Subsequences

补充原创地址：
http://zxi.mytechroad.com/blog/dynamic-programming/leetcode-730-count-different-palindromic-subsequences/

解题报告来自@花花酱的 youtube视频，可惜国内看不了。需要*。这里复制粘贴下。
原理是动态规划DP算法，按照长度来。
DP首先划分字符串，分为两种情况：
子字符串s[i~j]中，s[i]!=s[j] 或者 s[i]==s[j]
在s[i]==s[j]情况下，有分为三种情况
1. s[i+1~j-1]之间不含有字母s[i]
2. 含有1个字母s[i]
3. 含有》2个字母s[i]。
DP的递推过程如下图：

AC的代码如下

class Solution {
public:
    int countPalindromicSubsequences(string S) {
        int n=S.size();
        if(n==0){
            return 0;
        }
        long int M=1000000007;
        vector<vector<int>> dp (n,vector<int>(n,0));
        for(int i=0;i<n;i++){
            dp[i][i]=1;
        }
        //按照子问题的长度来构建
        for(int len=1;len<n;len++){
            for(int i=0;i<n-len;i++){
                int j=i+len;
                if(S[i]==S[j]){
                    dp[i][j]=dp[i+1][j-1]*2;
                    int l=i+1;
                    int r=j-1;
                    while(l<=r && S[l]!=S[i]) l++;
                    while(l<=r && S[r]!=S[i]) r--;
                    if(l==r){
                        dp[i][j]+=1;
                    }else if(l<r){
                        dp[i][j]-=dp[l+1][r-1];
                    }else{
                        dp[i][j]+=2;
                    }
                }else{
                    dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1];
                }
                dp[i][j]=(dp[i][j]+M)%M;//防止有的dp[][]<0
            }
        }
        return dp[0][n-1];
    }
};