[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 }      

轉載于:https://www.cnblogs.com/liuliu5151/p/10823249.html