Description

Given a string S, find the number of different non-empty palindromic subsequences in S, and return that number modulo 10^9 + 7.

A subsequence of a string S is obtained by deleting 0 or more characters from S.

A sequence is palindromic if it is equal to the sequence reversed.

Two sequences A_1, A_2, ... and B_1, B_2, ... are different if there is some i for which A_i != B_i.

Example 1:

Input:
S = 'bccb'
Output: 6
Explanation:
The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'.
Note that 'bcb' is counted only once, even though it occurs twice.

Example 2:

Input:
S = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
Output: 104860361
Explanation:
There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 10^9 + 7.

Note:

The length of S will be in the range [1, 1000].
Each character S[i] will be in the set {'a', 'b', 'c', 'd'}.

Solution

DP (using 3D array), time

大开眼界的一道题，原来用3D DP好多事情都会迎刃而解。。

Let dp[x][i][j] be the answer for the substring S[i...j] where S[i] == S[j] == 'a'+x. Note that since we only have 4 characters a, b, c, d, thus 0 <= x < 4. The DP formula goes as follows:

If S[i] != 'a'+x, then dp[x][i][j] = dp[x][i+1][j], note that here we leave the first character S[i] in the window out due to our definition of dp[x][i][j].
If S[j] != 'a'+x, then dp[x][i][j] = dp[x][i][j-1], leaving the last character S[j] out.
If S[i] == S[j] == 'a'+x, then dp[x][i][j] = 2 + dp[0][i+1][j-1] + dp[1][i+1][j-1] + dp[2][i+1][j-1] + dp[3][i+1][j-1]. When the first and last characters are the same, we need to count all the distinct palindromes (for each of a,b,c,d) within the sub-window S[i+1][j-1] plus the 2 palindromes contributed by the first and last characters. 注意这里为什么是加2？让我们回归到dp[x][i][j]的定义上，其包含的palindrome的最左和最右字符一定是x，所以推导dp[x][i][j]的时候必须将x放在其头尾，那么就有"x + subPalindromes + x", "xx", "x"这几种情况，加2就显而易见了。

Let n be the length of the input string S, The final answer would be dp[0][0][n-1] + dp[1][0][n-1] + dp[2][0][n-1] + dp[3][0][n-1] mod 1000000007.

考虑一下这种思路为什么2D DP是不够用的。假设dp[i][j]表示s[i...j]的palindrome sequence count，那么如果s[i] != s[j]，dp[i][j] = dp[i + 1][j] + dp[i][j - 1]是错的，因为子问题会有重复解。只有再添加一维x，指定字符，每个子问题才是独立的。

好吧还是有点懵。。

class Solution {
    public int countPalindromicSubsequences(String s) {
        int n = s.length();
        int mod = 1000000007;
        int[][][] dp = new int[4][n][n];
        
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                for (int k = 0; k < 4; ++k) {
                    char c = (char) ('a' + k);
                    
                    if (j == i) {
                        if (s.charAt(i) == c) {
                            dp[k][i][j] = 1;
                        }
                        continue;
                    }
                    
                    if (s.charAt(i) != c) {
                        dp[k][i][j] = dp[k][i + 1][j];
                    } else if (s.charAt(j) != c) {
                        dp[k][i][j] = dp[k][i][j - 1];
                    } else {
                        dp[k][i][j] = 2;
                        for (int x = 0; x < 4; ++x) {
                            dp[k][i][j] += dp[x][i + 1][j - 1];
                            dp[k][i][j] %= mod;
                        }
                    }
                }
            }
        }
        
        int res = 0;
        for (int k = 0; k < 4; ++k) {
            res += dp[k][0][n - 1];
            res %= mod;
        }
        
        return res;
    }
}