【动态规划】2484. 统计回文子序列数目

本文涉及知识点

动态规划汇总
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

LeetCode2484. 统计回文子序列数目

给你数字字符串 s ，请你返回 s 中长度为 5 的 回文子序列 数目。由于答案可能很大，请你将答案对 109 + 7 取余 后返回。
提示：
如果一个字符串从前往后和从后往前读相同，那么它是 回文字符串 。
子序列是一个字符串中删除若干个字符后，不改变字符顺序，剩余字符构成的字符串。
示例 1：
输入：s = “103301”
输出：2
解释：
总共有 6 长度为 5 的子序列：“10330” ，“10331” ，“10301” ，“10301” ，“13301” ，“03301” 。
它们中有两个（都是 “10301”）是回文的。
示例 2：
输入：s = “0000000”
输出：21
解释：所有 21 个长度为 5 的子序列都是 “00000” ，都是回文的。
示例 3：
输入：s = “9999900000”
输出：2
解释：仅有的两个回文子序列是 “99999” 和 “00000” 。
提示：
1 <= s.length <= 10⁴
s 只包含数字字符。

动态规划

一，dp1[i][j] 表示以s[i]开头s[j]结尾的长度为3 的回文子序列数量。
{ 0 s [ i ] ! = s [ j ] 0 i > = j j − i − 1 o t h e r

$$\begin{cases} 0 && s[i] != s[j] \\ 0 && i >= j\\ j-i-1 && other \\ \end{cases}$$ ⎩ ⎨ ⎧​00j−i−1​​s[i]!=s[j]i>=jother​
dp2[i][j]表示以s[i]开头 s[j1]结尾的长度为3的回文子序列数量。j1$\in$[i,j]。
$dp2[i][j]={\sum }_{j1:i}^{j}dp1[i][j1]$
dp3[i][j]表示以s[i1]开头s[j1]结尾的长度为3的回文子序列数量。i1,j1$\in$[i,j]
$dp3[i][j]={\sum }_{i1:0}^{j}dp2[i1][j]$
dp[i,j]表示以s[i]开始s[j]结尾的长度为5的回文子序列数量。其和就是答案。
如果s[i]==s[j] 就是 dp3[i+1][j-1]，否则为0
** 时间复杂度**：O(nn) 超时

代码

template<int MOD = 1000000007>
class C1097Int
{
public:
	C1097Int(long long llData = 0) :m_iData(llData% MOD)
	{

	}
	C1097Int  operator+(const C1097Int& o)const
	{
		return C1097Int(((long long)m_iData + o.m_iData) % MOD);
	}
	C1097Int& operator+=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData + o.m_iData) % MOD;
		return *this;
	}
	C1097Int& operator-=(const C1097Int& o)
	{
		m_iData = (m_iData + MOD - o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator-(const C1097Int& o)
	{
		return C1097Int((m_iData + MOD - o.m_iData) % MOD);
	}
	C1097Int  operator*(const C1097Int& o)const
	{
		return((long long)m_iData * o.m_iData) % MOD;
	}
	C1097Int& operator*=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData * o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator/(const C1097Int& o)const
	{
		return *this * o.PowNegative1();
	}
	C1097Int& operator/=(const C1097Int& o)
	{
		*this /= o.PowNegative1();
		return *this;
	}
	bool operator==(const C1097Int& o)const
	{
		return m_iData == o.m_iData;
	}
	bool operator<(const C1097Int& o)const
	{
		return m_iData < o.m_iData;
	}
	C1097Int pow(long long n)const
	{
		C1097Int iRet = 1, iCur = *this;
		while (n)
		{
			if (n & 1)
			{
				iRet *= iCur;
			}
			iCur *= iCur;
			n >>= 1;
		}
		return iRet;
	}
	C1097Int PowNegative1()const
	{
		return pow(MOD - 2);
	}
	int ToInt()const
	{
		return m_iData;
	}
private:
	int m_iData = 0;;
};
class Solution {
public:
	int countPalindromes(string s) {
		const int N = s.length();
		vector<vector<C1097Int<>>> dp1(N, vector<C1097Int<>>(N));
		auto dp2 = dp1, dp3 = dp1;
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				if (s[i] != s[j]) { continue; }
				dp1[i][j] = j - i - 1;
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				dp2[i][j] = dp2[i][j - 1] + dp1[i][j];
			}
		}		
		for (int i = N - 1; i >= 0; i--) {
			for (int j = i + 1; j < N; j++) {
				dp3[i][j] = ((i + 1) < N ? dp3[i + 1][j] : 0) + dp2[i][j];
			}
		}
		C1097Int<> biRet;
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				if (s[i] != s[j]) { continue; }
				biRet += dp3[i + 1][j - 1];
			}
		}
		return biRet.ToInt();
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

动态规划+前缀和

indexs[ch-‘a’]记录ch所有下标。
令最终回文子序列为t，则三册循环：
第一层循环通过ch枚举t[0]和t[4]，时间复杂度O($\sum$) 即O(10)。
第二层循环通过ch2枚举t[1]和t[3]，时间复杂度和第一层相同。
第三层循环通过inx = indexs[ch2-‘a’] 枚举t[3]在s中下标。
令s0为s[j]=ch ,且j < i的数量。
令s01 为 s[i]是t[3] 的t[0]和t[1]的方案数。
令s012 s[i]是他t[3]，t[0] t[1] t[2]的方案数。
t[4]为ch的方案数为：inx中大于i的数量，令其为s4。
则以s[i]为t3的总方案数为：s012s4。
$\forall$i $\in$ inx ,i1是其下一个元素。
令i1对应的s0、s01、s012分别为s1_、s01_ 和s012_。
s012_由两部分组成：
一，t[1]不是s[i] s012+ s01(i1-i)。
二，t1[1]是s[i] ，s0_*(i1-i-1)。
s01_ += s0_
时间复杂度：O(n$\sum \sum$)

代码

核心代码

template<int MOD = 1000000007>
class C1097Int
{
public:
	C1097Int(long long llData = 0) :m_iData(llData% MOD)
	{

	}
	C1097Int  operator+(const C1097Int& o)const
	{
		return C1097Int(((long long)m_iData + o.m_iData) % MOD);
	}
	C1097Int& operator+=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData + o.m_iData) % MOD;
		return *this;
	}
	C1097Int& operator-=(const C1097Int& o)
	{
		m_iData = (m_iData + MOD - o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator-(const C1097Int& o)
	{
		return C1097Int((m_iData + MOD - o.m_iData) % MOD);
	}
	C1097Int  operator*(const C1097Int& o)const
	{
		return((long long)m_iData * o.m_iData) % MOD;
	}
	C1097Int& operator*=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData * o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator/(const C1097Int& o)const
	{
		return *this * o.PowNegative1();
	}
	C1097Int& operator/=(const C1097Int& o)
	{
		*this /= o.PowNegative1();
		return *this;
	}
	bool operator==(const C1097Int& o)const
	{
		return m_iData == o.m_iData;
	}
	bool operator<(const C1097Int& o)const
	{
		return m_iData < o.m_iData;
	}
	C1097Int pow(long long n)const
	{
		C1097Int iRet = 1, iCur = *this;
		while (n)
		{
			if (n & 1)
			{
				iRet *= iCur;
			}
			iCur *= iCur;
			n >>= 1;
		}
		return iRet;
	}
	C1097Int PowNegative1()const
	{
		return pow(MOD - 2);
	}
	int ToInt()const
	{
		return m_iData;
	}
private:
	int m_iData = 0;;
};
class Solution {
public:
	int countPalindromes(string s) {
		vector<int> indexs[10];
		for (int i = 0; i < s.length(); i++) {
			indexs[s[i] - '0'].emplace_back(i);
		}
		C1097Int<> biRet;
		auto Do = [&](const vector<int>& inx04, const vector<int>& inx13) {
			C1097Int<>  s01 = 0, s012 = 0;
			int i0=0,i4 = 0;
			int pre = -1;
			for (int i3 : inx13) {
				while ((i4 < inx04.size()) && (inx04[i4] <= i3 )) {
					i4++;
				}
				if (-1 != pre) {
					s012 += s01 * (i3 - pre);
					s012 += i0 * (i3 - pre - 1);
					s01 += i0;
					biRet += s012 * (inx04.size() - i4);
				}
				while ((i0 < inx04.size()) && (inx04[i0] < i3)) {
					i0++;
				}
				pre = i3;
			}
		};
		for (int i04 = 0; i04 < 10; i04++) {
			for (int i13 = 0; i13 < 10; i13++) {
				Do(indexs[i04], indexs[i13]);
			}
		}		
		return biRet.ToInt();
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

单元测试

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{
	Assert::AreEqual(t1, t2);
}

template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
	Assert::AreEqual(v1.size(), v2.size());
	for (int i = 0; i < v1.size(); i++)
	{
		Assert::AreEqual(v1[i], v2[i]);
	}
}

template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
	sort(vv1.begin(), vv1.end());
	sort(vv2.begin(), vv2.end());
	Assert::AreEqual(vv1.size(), vv2.size());
	for (int i = 0; i < vv1.size(); i++)
	{
		AssertEx(vv1[i], vv2[i]);
	}
}

namespace UnitTest
{	
	string s;
	TEST_CLASS(UnitTest)
	{
	public:
		TEST_METHOD(TestMethod00)
		{
			s = "103301";
			auto res = Solution().countPalindromes(s);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod01)
		{
			s = "0000000";
			auto res = Solution().countPalindromes(s);
			AssertEx(21, res);
		}
		TEST_METHOD(TestMethod02)
		{
			s = "9999900000";
			auto res = Solution().countPalindromes(s);
			AssertEx(2, res);
		}
	};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

如果有不明白的，请加文末QQ群。

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等

课程
https://edu.csdn.net/lecturer/6176

相关推荐

法文章，请点击《算法与数据汇总》。
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
|闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。|
| 子墨子言之

：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙，那算法就是他的是睛|

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实

现。