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)，然而因?yàn)?code>bcc兩側(cè)的字符（a和a）一樣，所以又可以組成新的回文串，數(shù)目等于num(bcc)，最后字符a與a也能組成一個(gè)新的回文串aa所以結(jié)果+1
由此可見當(dāng)字符串為abccx時(shí)，num(abccx) = num(abcc) + num(bccx) - num(bcc)

由上面的方法，可以推出DP的解題方法：
假設(shè)有二維數(shù)組DP，DP[i][j]代表了從字符串的第i個(gè)字符到第j個(gè)字符之間包含了多少回文串序列。
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];
}