C++刷LeetCode（730. 统计不同回文子序列***）【动态规划】【数学归纳】

糖逗

题目描述：

1. 给定一个字符串 S，找出 S 中不同的非空回文子序列个数，并返回该数字与 10^9 + 7 的模。
   
2. 
   
3. 通过从 S 中删除 0 个或多个字符来获得子序列。
   
4. 
   
5. 如果一个字符序列与它反转后的字符序列一致，那么它是回文字符序列。
   
6. 
   
7. 如果对于某个  i，A_i != B_i，那么 A_1, A_2, ... 和 B_1, B_2, ... 这两个字符序列是不同的。
   
8. 
   
9.  
   
10. 
    
11. 示例 1：
    
12. 
    
13. 输入：
    
14. S = 'bccb'
    
15. 输出：6
    
16. 解释：
    
17. 6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
    
18. 注意：'bcb' 虽然出现两次但仅计数一次。
    
19. 示例 2：
    
20. 
    
21. 输入：
    
22. S = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
    
23. 输出：104860361
    
24. 解释：
    
25. 共有 3104860382 个不同的非空回文子序列，对 10^9 + 7 取模为 104860361。
    
26.  
    
27. 
    
28. 提示：
    
29. 
    
30. 字符串 S 的长度将在[1, 1000]范围内。
    
31. 每个字符 S[i] 将会是集合 {'a', 'b', 'c', 'd'} 中的某一个。
    
32.  
    
33. 
    
34. 来源：力扣（LeetCode）
    
35. 链接：https://leetcode-cn.com/problems/count-different-palindromic-subsequences
    
36. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. private:
   
3.     const int mode = 1e9+7;
   
4. public:
   
5.     int countPalindromicSubsequences(string S) {
   
6.         int len = S.size();
   
7.         vector<vector<int> >dp(len, vector<int>(len, 0));
   
8.         //dp[i][j]表示下标i到j区间内的回文字符串个数（包括两端）
   
9.         //初始化
   
10.         for(int i = 0; i < len; i++){
    
11.             dp[i][i] = 1;
    
12.         }
    
13.         //动态规划
    
14.         for(int k= 2; k <= len; k++){
    
15.             for(int i = 0; i < len - k + 1; i++){
    
16.                 int j = i + k - 1;
    
17.                 if(S[i] != S[j]){
    
18.                     dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];
    
19.                 }else{
    
20.                     dp[i][j] = dp[i + 1][j - 1] * 2;
    
21.                     int l = i + 1, r = j - 1;
    
22.                     while (l <= r && S[l] != S[i]) l += 1;
    
23.                     while (l <= r && S[r] != S[i]) r -= 1;
    
24.                     if (l > r) dp[i][j] += 2;
    
25.                     else if (l == r) dp[i][j] += 1;
    
26.                     else dp[i][j] -= dp[l + 1][r - 1];
    
27.                 }
    
28.                 dp[i][j] = dp[i][j] < 0 ? dp[i][j] + mode : dp[i][j] % mode;
    
29.             }
    
30.         }
    
31.         return dp[0][len-1];
    
32.     }
    
33. };

复制代码

参考链接：https://leetcode-cn.com/problems ... en-lei-tao-lun-by-/