[leetcode]730. Count Different Palindromic Subsequences计数不同的回文子序列的个数

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'}.

题意：

计数不同的回文子序列的个数

Solution1：DP

code

 1 /*
 2 Recursion with memoization
 3 Time complexity: O(n^2)
 4 Space complexity: O(n^2)
 5 */
 6 
 7 class Solution {
 8      private int[][] memo;
 9     // requirement: "return that number modulo 10^9 + 7"
10     private static final int kMod = 1000000007;
11     public int countPalindromicSubsequences(String S) {
12         int n = S.length();
13         memo = new int[n][n];
14         return count(S.toCharArray(), 0, n - 1);
15     }
16 
17     private int count(char[] s, int i, int j) {
18         if (i > j) return 0;
19         if (i == j) return 1;
20         if (memo[i][j] > 0) return memo[i][j];
21         // 根据题意，count结果可能很大，用long更保险
22         long result = 0;
23         // 当前首尾字符相同
24         if (s[i] == s[j]) {
25             //  count(中间子串解) *2
26             result += count(s, i + 1, j - 1) * 2;
27             int l = i + 1;
28             int r = j - 1;
29             while (l <= r && s[l] != s[i]) ++l;
30             while (l <= r && s[r] != s[i]) --r;
31             // case1: 中间子串的字符中，都不同于当前首尾字符
32             if (l > r) result += 2;
33             // case2：中间子串的字符中，有1个字符等于当前首尾字符
34             else if (l == r) result += 1;
35             // case3: 中间子串的2个首尾字符，等于当前首尾字符
36             else result -= count(s, l + 1, r - 1);
37         }
38         // 当前首尾字符不同
39         else {
40             result = count(s, i, j - 1)
41                     + count(s, i + 1, j)
42                     - count(s, i + 1, j - 1);
43         }
44         // to avoid stack overflow
45         memo[i][j] = (int)((result + kMod) % kMod);
46         return memo[i][j];
47     }
48 }