【动态规划】2484. 统计回文子序列数目_业界新闻

发布时间:2024-07-18 12:19

阅读量:3

本文涉及知识点

动态规划汇总
 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 的回文子序列数量。
$\begin{cases} 0 && s[i] != s[j] \\ 0 && i >= j\\ j-i-1 && other \\ \end{cases}$
dp2[i][j]表示以s[i]开头 s[j1]结尾的长度为3的回文子序列数量。j1 $\in$ [i,j]。
$\sum_{j1:i}^{j}dp1[i][j1]$
dp3[i][j]表示以s[i1]开头s[j1]结尾的长度为3的回文子序列数量。i1,j1 $\in$ [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(); 	} };

动态规划+前缀和

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(); 	} };

单元测试

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); 		} 	}; }