Numbers of palindromic subsequen

Description:

Find how many palindromic subsequence (need not necessarily be distinct) can be formed
in a given string. Note that the empty string is not considered as a palindrome.

Example:

Input : str = "abcd"
Output : 4
Explanation :- palindromic subsequence are : "a" ,"b", "c" ,"d"
Input : str = "aab"
Output : 4
Explanation :- palindromic subsequence are :"a", "a", "b", "aa"
Input : str = "aaaa"
Output : 15

解题方法：

这道题首先可以用递归的方法解决，这也是想到DP的途径：
比如给定字符串abcca我们以num(abcca)来代表Numbers of palindromic subsequence
那么num(abcca) = num(abcc) + num(bcca) - num(bcc) + num(bcc) + num(aa) = num(abcc) + num(bcca) + 1
解释：abcc和bcca有重合部分bcc，所以我们减去num(bcc)，然而因为bcc两侧的字符（a和a）一样，所以又可以组成新的回文串，数目等于num(bcc)，最后字符a与a也能组成一个新的回文串aa所以结果+1
由此可见当字符串为abccx时，num(abccx) = num(abcc) + num(bccx) - num(bcc)

由上面的方法，可以推出DP的解题方法：
假设有二维数组DP，DP[i][j]代表了从字符串的第i个字符到第j个字符之间包含了多少回文串序列。
so, if string[i] == string[j], DP[i][j] = DP[i][j - 1] + DP[i + 1][j] + 1;
otherwise, DP[i][j] = DP[i][j - 1] + DP[i + 1][j] - DP[i + 1][j - 1];

Time Complexity：

O(N^2)

完整代码：

int nps(string& str) {
    int len = str.size();
    if(!len)
        return 0;
    vector<vector<int>> DP(len + 1, vector<int>(len + 1, 0));
    //init
    for(int i = 0; i <= len; i++)
        DP[i][i] = 1;
    //DP
    for(int L = 2; L <= len; L++) {
        for(int i = 1; i + L - 1 <= len; i++) {
            int j = i + L - 1;
            if(str[i - 1] == str[j - 1])
                DP[i][j] = DP[i][j - 1] + DP[i + 1][j] + 1;
            else
                DP[i][j] = DP[i][j - 1] + DP[i + 1][j] - DP[i + 1][j - 1];
        }
    }
    return DP[1][len];
}