本文涉及知识点

C++动态规划 划分型

LeetCode3144. 分割字符频率相等的最少子字符串

给你一个字符串 s ，你需要将它分割成一个或者更多的 平衡 子字符串。比方说，s == “ababcc” 那么 (“abab”, “c”, “c”) ，(“ab”, “abc”, “c”) 和 (“ababcc”) 都是合法分割，但是 (“a”, “bab”, “cc”) ，(“aba”, “bc”, “c”) 和 (“ab”, “abcc”) 不是，不平衡的子字符串用粗体表示。
请你返回 s 最少 能分割成多少个平衡子字符串。
注意：一个 平衡 字符串指的是字符串中所有字符出现的次数都相同。
示例 1：
输入：s = “fabccddg”
输出：3
解释：
我们可以将 s 分割成 3 个子字符串：("fab, “ccdd”, “g”) 或者 (“fabc”, “cd”, “dg”) 。
示例 2：
输入：s = “abababaccddb”
输出：2
解释：
我们可以将 s 分割成 2 个子字符串：(“abab”, “abaccddb”) 。
提示：
1 <= s.length <= 1000
s 只包含小写英文字母。

动态规划 划分型

Is[i][j]记录s[i…j]是否是平衡字符串。cnt[k]记录nums[i…j]中字符ch-‘a’的数量。nums[i…j]迭代成nums[i…j+1]时，只需要 k =nums[j+1]-‘a’, cnt[k]++。
cnt1记录cnt中，非0字符的数量。cnt1 +=（1==cnt[k]）。
iMax 记录 最多字符的数量。iMax = max(iMax,cnt[k])。
is[i][j] = (j-i+1) == iMax*cnt1。

动态规划的状态表示

dp[i] 表示划分完前i个元素的最少子串。空间复杂度😮(n)。

动态规划的填报顺序

枚举前置状态 i = 0 to n-1

动态规划的转移方程

如果Is[i][j]成立
MinSelf(dp[j+1],dp[i]+1)
单个状态转移时间复杂度：O(n) 总时间复杂度：O(nn)。

动态规划的初始值

dp[0]=0，其它全部为INT_MAX/2。

动态规划的返回值

dp.back

代码

核心代码

class Solution {
		public:
			int minimumSubstringsInPartition(string s) {
				const int N = s.length();
				vector<vector<bool>> can(N, vector<bool>(N));
				for (int i = 0; i < N; i++) {
					int cnt[26] = { 0 };
					int cnt1=0, iMax = 0;
					for (int j = i; j < N; j++) {
						auto& tmp = cnt[s[j] - 'a'];
						tmp ++;
						cnt1 += (1 == tmp);
						iMax = max(iMax, tmp);
						can[i][j] = (iMax * cnt1 == j - i + 1);
					}
				}
				vector<int> dp(N + 1, N);
				dp[0] = 0;
				for (int i = 0; i < N; i++) {
					for (int j = i; j < N; j++) {
						if (!can[i][j])continue;
						dp[j + 1] = min(dp[j + 1], dp[i] + 1);
					}
				}
				return dp.back();
			}
		};

单元测试

	string s;
		TEST_METHOD(TestMethod11)
		{
			s = "fabccddg";
			auto res = Solution().minimumSubstringsInPartition(s);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod12)
		{
			s = "abababaccddb";
			auto res = Solution().minimumSubstringsInPartition(s);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod13)
		{
			s="abbcabaa";
			auto res = Solution().minimumSubstringsInPartition(s);
			AssertEx(4, res);
		}