2026-07-03：划分二进制字符串的最小费用。用go语言，有一个只由 0 和 1 组成的二进制字符串 s，以及两个代价 encCost 和 flatCost。

把字符串 s 划分成若干个连续的片段（分段）。一开始把整个字符串视为一个片段；允许不断继续把某个片段拆成两个相邻的片段，直到得到最终的划分方案。

对任意某个片段，设它的长度为 L，并且该片段中 1 的数量为 X（即敏感元素的个数）：

• 若 X = 0（片段里没有敏感元素），则该片段的费用为 flatCost。

• 若 X > 0，则该片段的费用为 L × X × encCost。

拆分规则：

如果某个片段的长度是偶数，那么可以把它平均切成两个长度相同的连续片段。此时这次拆分产生的新总费用等于这两个子片段费用之和。

要求：在所有满足规则的有效划分中，求总费用的最小可能值，并返回这个最小总费用。

1 <= s.length <= 100000。

s 仅由 ‘0’ 和 ‘1’ 组成。

1 <= encCost, flatCost <= 100000。

输入： s = “1010”, encCost = 2, flatCost = 1。

输出： 6。

解释：

整个字符串 s = “1010” 长度为 4，包含 2 个敏感元素，费用为 4 * 2 * 2 = 16。

由于长度为偶数，它可以被拆分为 “10” 和 “10”。每个分段长度为 2 且包含 1 个敏感元素，因此每个分段的费用为 2 * 1 * 2 = 4，总计 8。

将两个分段继续拆分为四个单字符分段，得到 “1”、“0”、“1” 和 “0”。包含 “1” 的分段长度为 1 且恰好有一个敏感元素，费用为 1 * 1 * 2 = 2；而包含 “0” 的分段没有敏感元素，因此费用为 flatCost = 1。

因此总费用为 2 + 1 + 2 + 1 = 6，这是最小可能的总费用。

题目来自力扣3864。

一、代码整体执行分步拆解

步骤1：预处理前缀和数组，快速求任意区间1的总数

1. 字符串长度为n，创建长度n+1的前缀和数组sum，sum[0]=0。
2. 遍历字符串每一位，sum[i+1] = sum[i] + 当前字符转数字（0或1）。
3. 作用：对于任意左闭右开区间[l, r)，区间内1的总数X = sum[r] - sum[l]，O(1)查询任意片段1的数量，避免重复遍历统计。

步骤2：定义递归DFS函数dfs(l, r)：求区间[l, r)片段的最小总费用

函数输入l左边界、r右边界，代表原字符串从下标l到r-1的子串片段，返回该片段所有合法拆分方案里的最小费用，分4步执行：

分支1：当前片段全是0（X=0）

通过前缀和算出区间1总数X=sum[r]-sum[l]，若X=0：
该片段不能拆分优化（无论长度奇偶，费用固定为flatCost），直接返回flatCost。

分支2：先计算「不拆分」方案的费用

当前片段含1（X>0），不做任何拆分、直接保留整个片段的费用：
不拆分费用 = 片段长度 × 片段1总数 × encCost
把该值作为当前临时最优解res。

分支3：判断是否允许拆分，若允许则计算拆分后的费用并更新最小值

1. 计算当前片段长度len = r - l，只有len是偶数才能对半拆分；奇数直接跳过拆分逻辑。
2. 可拆分时，取中间分割点m=(l+r)/2，把片段均分左右两段[l,m)、[m,r)。
3. 递归分别求出左段最小费用dfs(l,m)、右段最小费用dfs(m,r)，两段相加得到「拆分一次」的总费用。
4. 对比临时最优解res和拆分总费用，取更小的值更新res。

分支4：返回当前片段的最小费用res

无论是否拆分，最终返回该区间能得到的最小费用。

步骤3：入口调用与结果转换

1. 完整字符串对应区间[0, n)，调用dfs(0, n)得到整型最小总费用。
2. 将结果转为int64类型返回，防止数值溢出。

步骤4：主函数样例执行完整流程（s=1010，n=4）

1. 预处理前缀和：sum数组为[0,1,1,2,2]
2. 调用dfs(0,4)：
   • X=sum[4]-sum[0]=2≠0，片段长度4为偶数
   • 不拆分费用：4×2×2=16，res初始=16
   • 中点m=2，递归计算dfs(0,2)+dfs(2,4)
     • 计算dfs(0,2)（子串"10"，L=2，X=1）
       X=1≠0，不拆分费用2×1×2=4；长度2偶数，中点m=1
       递归dfs(0,1)+dfs(1,2)
       • dfs(0,1)（字符1，L=1奇数）：X=1，费用1×1×2=2，不可拆分，返回2
       • dfs(1,2)（字符0，X=0）：直接返回flatCost=1
         两段和=3，对比原值4，更新res=3，返回3
     • 计算dfs(2,4)（子串"10"），逻辑同上，返回3
   • 两段总和3+3=6，对比初始res=16，更新res=6
3. dfs(0,4)最终返回6，输出结果6，和样例匹配。

二、算法存在的性能缺陷（针对原题数据范围1e5）

当前实现是纯暴力递归，无记忆化缓存：
同一个区间[l,r)会被多次重复递归计算；当字符串长度1e5时，递归深度极高、重复计算爆炸，会直接栈溢出+超时，仅能处理极小长度测试用例。

三、时间复杂度 & 额外空间复杂度（分两种场景）

1. 现有无记忆化暴力递归版本（代码原生实现）

时间复杂度

设字符串长度为n，每次偶数区间都会分裂成两个等长子区间，形成满二叉拆分树：
拆分树节点总数为 O(n)，但无记忆缓存，大量区间重复遍历，最坏情况时间复杂度为O(2ⁿ)，指数级，仅n≤20可运行，n=1e5完全不可用。

额外空间复杂度

1. 前缀和数组：长度n+1 → O(n)
2. 递归调用栈：每次对半拆分，栈最大深度 log₂n
   总额外空间：O(n)（前缀和数组为主导项）

2. 优化后增加记忆化DP（适配题目n≤1e5的标准解法，补充参考）

若增加记忆化哈希/区间DP缓存每个dfs(l,r)结果，每个唯一区间仅计算一次：

时间复杂度

所有合法拆分区间总数为O(n)，每个区间O(1)计算，整体O(n)

额外空间复杂度

前缀和数组O(n) + DP记忆缓存O(n) + 递归栈O(logn)，总空间仍为O(n)

Go完整代码如下：

packagemainimport("fmt")funcminCost(sstring,encCost,flatCostint)int64{n:=len(s)sum:=make([]int,n+1)fori,ch:=ranges{sum[i+1]=sum[i]+int(ch-'0')}// 计算子串 [l, r) 的最小费用，注意区间是左闭右开，方便计算vardfsfunc(int,int)intdfs=func(l,rint)int{x:=sum[r]-sum[l]ifx==0{returnflatCost}// 不拆分res:=(r-l)*x*encCost// 拆分if(r-l)%2==0{m:=(l+r)/2res=min(res,dfs(l,m)+dfs(m,r))}returnres}returnint64(dfs(0,n))}funcmain(){s:="1010"encCost:=2flatCost:=1result:=minCost(s,encCost,flatCost)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-defminCost(s:str,encCost:int,flatCost:int)->int:n=len(s)# 前缀和，记录 '1' 的个数prefix_sum=[0]*(n+1)fori,chinenumerate(s):prefix_sum[i+1]=prefix_sum[i]+int(ch)# 记忆化搜索，避免重复计算memo={}defdfs(l:int,r:int)->int:# 子串为 [l, r)，左闭右开if(l,r)inmemo:returnmemo[(l,r)]ones=prefix_sum[r]-prefix_sum[l]zeros=(r-l)-ones# 全是 0，直接压平ifones==0:memo[(l,r)]=flatCostreturnflatCost# 不拆分：按位编码res=(r-l)*ones*encCost# 如果长度是偶数，尝试拆分if(r-l)%2==0:mid=(l+r)//2res=min(res,dfs(l,mid)+dfs(mid,r))memo[(l,r)]=resreturnresreturndfs(0,n)defmain():s="1010"encCost=2flatCost=1result=minCost(s,encCost,flatCost)print(result)if__name__=="__main__":main()

C++完整代码如下：

#include<iostream>#include<vector>#include<string>#include<functional>#include<algorithm>#include<unordered_map>usingnamespacestd;longlongminCost(string s,intencCost,intflatCost){intn=s.length();vector<int>prefix_sum(n+1,0);// 构建前缀和for(inti=0;i<n;i++){prefix_sum[i+1]=prefix_sum[i]+(s[i]-'0');}// 记忆化搜索，使用字符串作为键存储状态unordered_map<string,int>memo;// DFS函数function<int(int,int)>dfs=[&](intl,intr)->int{// 生成状态键string key=to_string(l)+","+to_string(r);if(memo.find(key)!=memo.end()){returnmemo[key];}intones=prefix_sum[r]-prefix_sum[l];// 全是0，直接压平if(ones==0){memo[key]=flatCost;returnflatCost;}// 不拆分：按位编码intres=(r-l)*ones*encCost;// 如果长度是偶数，尝试拆分if((r-l)%2==0){intmid=(l+r)/2;res=min(res,dfs(l,mid)+dfs(mid,r));}memo[key]=res;returnres;};return(longlong)dfs(0,n);}intmain(){string s="1010";intencCost=2;intflatCost=1;longlongresult=minCost(s,encCost,flatCost);cout<<result<<endl;return0;}