入门力扣自学笔记58 C++ （题目编号730）（未理解）

730. 统计不同回文子序列

题目：

给定一个字符串 s，返回 s 中不同的非空「回文子序列」个数 。

通过从 s 中删除 0 个或多个字符来获得子序列。

如果一个字符序列与它反转后的字符序列一致，那么它是「回文字符序列」。

如果有某个 i , 满足 ai != bi ，则两个序列 a1, a2, ... 和 b1, b2, ... 不同。

注意：

结果可能很大，你需要对  + 7 取模 。

示例 1：

输入：s = 'bccb'
输出：6
解释：6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意：'bcb' 虽然出现两次但仅计数一次。

示例 2：

输入：s = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
输出：104860361
解释：共有 3104860382 个不同的非空回文子序列，104860361 对 + 7 取模后的值。

提示：

1 <= s.length <= 1000
s[i] 仅包含 'a', 'b', 'c' 或 'd' 

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-different-palindromic-subsequences
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

动态规划+记忆化搜索

代码：

class Solution {
public:int countPalindromicSubsequences(string s) {int n = s.size();vector<vector<int>> f(n,vector<int>(n,0));for(int i=0;i<n;i++)f[i][i]=1;const int mod = 1e9+7;for(int i=n-2;i>=0;i--){for(int j=i+1;j<n;j++){if(s[i]!=s[j])f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1];else{f[i][j] = f[i+1][j-1]*2+2;int l=i+1,r=j-1;while(l<=r&&s[l]!=s[i])l++;while(l<=r&&s[r]!=s[i])r--;// 第2.1种情况 中间有1个s[i]if(l==r)f[i][j]--;// 第2.2种情况 中间有≥2个s[i]else if(l<r)f[i][j] -=2+f[l+1][r-1];}f[i][j]=(f[i][j]>=0)?f[i][j]%mod:f[i][j]+mod;}}return f[0][n-1];}
};