C++刷LeetCode（730. 统计不同回文子序列***）【动态规划】【数学归纳】
题目描述：给定一个字符串 S，找出 S 中不同的非空回文子序列个数，并返回该数字与 10^9 + 7 的模。
通过从 S 中删除 0 个或多个字符来获得子序列。
如果一个字符序列与它反转后的字符序列一致，那么它是回文字符序列。
如果对于某个 i，A_i != B_i，那么 A_1, A_2, ... 和 B_1, B_2, ... 这两个字符序列是不同的。
示例 1：
输入：
S = 'bccb'
输出：6
解释：
6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意：'bcb' 虽然出现两次但仅计数一次。
示例 2：
输入：
S = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
输出：104860361
解释：
共有 3104860382 个不同的非空回文子序列，对 10^9 + 7 取模为 104860361。
提示：
字符串 S 的长度将在范围内。
每个字符 S 将会是集合 {'a', 'b', 'c', 'd'} 中的某一个。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-different-palindromic-subsequences
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
private:
const int mode = 1e9+7;
public:
int countPalindromicSubsequences(string S) {
int len = S.size();
vector<vector<int> >dp(len, vector<int>(len, 0));
//dp表示下标i到j区间内的回文字符串个数（包括两端）
//初始化
for(int i = 0; i < len; i++){
dp = 1;
}
//动态规划
for(int k= 2; k <= len; k++){
for(int i = 0; i < len - k + 1; i++){
int j = i + k - 1;
if(S != S){
dp = dp + dp - dp;
}else{
dp = dp * 2;
int l = i + 1, r = j - 1;
while (l <= r && S != S) l += 1;
while (l <= r && S != S) r -= 1;
if (l > r) dp += 2;
else if (l == r) dp += 1;
else dp -= dp;
}
dp = dp < 0 ? dp + mode : dp % mode;
}
}
return dp;
}
};
参考链接：https://leetcode-cn.com/problems/count-different-palindromic-subsequences/solution/dong-tai-gui-hua-dui-qu-jian-dpfen-lei-tao-lun-by-/
页:
[1]