题目：
给你一个字符串 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 <= 1000s只包含小写英文字母。
示例3 已经提示使用 动态规划， 而不是贪心算法
但从题意分析来说：对于没有 很清晰思路 的问题，都可以从答案的出发 往前分析
最终拆分的结果中的每个子字符串， 其各个字符出现的次数相同
问题出现在如果多个子字符串中有相同字符，那么这个字符其实有机会出现在前一个 或者 后一个 子字符串中
这就说明不能使用贪心算法（贪心只会将它放在前一个子字符串中）
对于动态规划，先考虑寻找子问题，然后需要考虑 定义dp数组 和 寻找递推公式
其实对于大多数题解给出的动态规划都属于自底向上的编码方式，也即定义dp数组，然后依靠dp数组求解问题
动态规划还有另外一种自顶向下的方式，也即记忆化搜索。相当于将dp数组转变成一个dfs的深搜函数
自顶向下记忆化搜索
思路：
首先说明，分割方案是一定存在的，因为单个字母是平衡的，我们一定可以把 s 划分成 n 个平衡子串。
一、寻找子问题
示例 1 的 s = fabccddg，枚举最后一段的长度：
最后一段分割出一个长为 1 的子串，即 g，这是平衡的，问题变成剩余字符串 fabccdd 最少能分割出多少个平衡子串。
最后一段分割出一个长为 2 的子串，即 dg，这是平衡的，问题变成剩余字符串 fabccd 最少能分割出多少个平衡子串。
……
在这个过程中，我们只需要知道剩余字符串的长度，因为剩余字符串一定是 s 的一个前缀。
这些问题都是和原问题相似的、规模更小的子问题，可以用递归解决。
注 1：从右往左思考，主要是为了方便把递归翻译成递推。从左往右思考也是可以的。
注 2：动态规划有「选或不选」和「枚举选哪个」两种基本思考方式。在做题时，可根据题目要求，选择适合题目的一种来思考。本题用到的是「枚举选哪个」。
二、状态定义与状态转移方程
根据上面的讨论，我们只需要在递归过程中跟踪以下信息：
i：剩余字符串是 s[0] 到 s[i]。
因此，定义状态为 dfs(i)，表示当剩余字符串是 s[0] 到 s[i] 时，最少能分割出多少个平衡子串。
枚举最后一段从 s[j] 到 s[i]，如果这个子串是平衡的，那么接下来要解决的问题是：当剩余字符串是 s[0] 到 s[j − 1] 时，最少能分割出多少个平衡子串，即 dfs(j − 1)。
枚举所有小于等于 i 的 j，取 dfs(j − 1) 的最小值，即
dfs(i) = min dfs(j - 1) + 1 其中 j ∈ [0, i], s[j] 到 s[i] 是平衡子串。
如何快速判断子串是平衡的呢？
我们可以在倒序枚举 j 的同时，用一个哈希表（或者数组）统计每个字符的出现次数。如果子串中每个字母的出现次数都相等，那么子串是平衡的。
优化：设子串中有 k 种字母，字母出现次数的最大值为 maxCnt。子串是平衡的，当且仅当子串长度 i − j + 1 等于 k * maxCnt。
递归边界：dfs(−1)=0。
递归入口：dfs(n − 1)，也就是答案。
三、递归搜索 + 保存递归返回值 = 记忆化搜索
考虑到整个递归过程中有大量重复递归调用（递归入参相同）。由于递归函数没有副作用，同样的入参无论计算多少次，算出来的结果都是一样的，因此可以用记忆化搜索来优化：
如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 memo 数组中。
如果一个状态不是第一次遇到（memo 中保存的结果不等于 memo 的初始值），那么可以直接返回 memo 中保存的结果。
注意：memo 数组的初始值一定不能等于要记忆化的值！例如初始值设置为 0，并且要记忆化的 dfs(i) 也等于 0，那就没法判断 0 到底表示第一次遇到这个状态，还是表示之前遇到过了，从而导致记忆化失效。一般把初始值设置为 −1。
本题当 i ≥ 0 时，dfs(i) 一定是正数（因为任意字符串都存在合法分割方案），所以 memo 数组初始化成 0 也可以。
代码：
class Solution {
public:
int minimumSubstringsInPartition(string s) {
int n = s.size();
vector<int> memo(n); // 存储记忆化搜索结果
auto dfs = [&](auto&& dfs, int i) -> int { // dfs的返回结果是s[0, i]最少分割的子字符串数
if (i < 0) return 0;
int& res = memo[i];
if (res) return res;
res = INT_MAX;
int cnt[26]{}, k = 0, max_cnt = 0;
for (int j = i; j >= 0; j--) {
k += cnt[s[j] - 'a']++ == 0;
max_cnt = max(max_cnt, cnt[s[j] - 'a']);
if (i - j + 1 == k * max_cnt) res = min(res, dfs(dfs, j - 1) + 1);
}
return res;
};
return dfs(dfs, n - 1);
}
};
自底向上动态规划
思路：
我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。
具体来说，f[i + 1] 的定义和 dfs(i) 的定义是一样的，都表示当剩余字符串是 s[0] 到 s[i] 时，最少能分割出多少个平衡子串。这里 +1 是为了把 dfs(−1) 这个状态也翻译过来，这样我们可以把 f[0] 作为初始值。
相应的递推式（状态转移方程）也和 dfs 一样：
f[i + 1]= min f[j] + 1, j ∈ [0, i], s[j] 到 s[i] 是平衡子串。
初始值 f[0]=0，翻译自递归边界 dfs(−1)=0。
答案为 f[n]，翻译自递归入口 dfs(n−1)。
代码：
class Solution {
public:
int minimumSubstringsInPartition(string s) {
int n = s.length();
vector<int> f(n + 1, INT_MAX);
f[0] = 0;
for (int i = 0; i < n; i++) {
int cnt[26]{}, k = 0, max_cnt = 0;
for (int j = i; j >= 0; j--) {
k += cnt[s[j] - 'a']++ == 0;
max_cnt = max(max_cnt, cnt[s[j] - 'a']);
if (i - j + 1 == k * max_cnt) {
f[i + 1] = min(f[i + 1], f[j] + 1);
}
}
}
return f[n];
}
};