Readme

3864.Minimum-Cost-to-Partition-a-Binary-String

根据题意的规则，非常容易想到递归。当长度为奇数时，无法分割，只能直接算direct cost。当长度为偶数时，只有两种策略：不分割直接算direct cost，或者对半分割递归处理。

对于这样的递归函数，参数必然有两个，就是左右端点的位置。但是本题的数据量n=1e5，理论上可能需要访问的状态有n^2种。即使记忆化，空间上也是不可能的。那么怎么办呢？

其实关键点在于本题的规则有着特殊性，使得需要遍历的状态并不多。每个状态看似有两个分支，但是其中一个分支（也就是不split）并不需要继续往下递归。所以极端情况下，假设长度为n的数组且n是二次幂，那么我们需要访问：

• 第一层：[0,n-1]
• 第二层：[0,n/2),[n/2,n-1],
• 第三层[0,n/4),[n/4,n/2),[n/2,3/4n),[3/4n,n)...
• 我们最多递归到最底层每个区间只有一个元素。

我们发现每层的区间并不重叠，且不同分支的探索也不会有任何重复的机会，所以最多访问的区间也就是2*n个。因此本题完全不需要借助记忆化，暴力递归即可。