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

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的总数字符串长度为n创建长度n1的前缀和数组sumsum[0]0。遍历字符串每一位sum[i1] sum[i] 当前字符转数字0或1。作用对于任意左闭右开区间[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当前片段全是0X0通过前缀和算出区间1总数Xsum[r]-sum[l]若X0该片段不能拆分优化无论长度奇偶费用固定为flatCost直接返回flatCost。分支2先计算「不拆分」方案的费用当前片段含1X0不做任何拆分、直接保留整个片段的费用不拆分费用 片段长度 × 片段1总数 × encCost把该值作为当前临时最优解res。分支3判断是否允许拆分若允许则计算拆分后的费用并更新最小值计算当前片段长度len r - l只有len是偶数才能对半拆分奇数直接跳过拆分逻辑。可拆分时取中间分割点m(lr)/2把片段均分左右两段[l,m)、[m,r)。递归分别求出左段最小费用dfs(l,m)、右段最小费用dfs(m,r)两段相加得到「拆分一次」的总费用。对比临时最优解res和拆分总费用取更小的值更新res。分支4返回当前片段的最小费用res无论是否拆分最终返回该区间能得到的最小费用。步骤3入口调用与结果转换完整字符串对应区间[0, n)调用dfs(0, n)得到整型最小总费用。将结果转为int64类型返回防止数值溢出。步骤4主函数样例执行完整流程s1010n4预处理前缀和sum数组为[0,1,1,2,2]调用dfs(0,4)Xsum[4]-sum[0]2≠0片段长度4为偶数不拆分费用4×2×216res初始16中点m2递归计算dfs(0,2)dfs(2,4)计算dfs(0,2)子串10L2X1X1≠0不拆分费用2×1×24长度2偶数中点m1递归dfs(0,1)dfs(1,2)dfs(0,1)字符1L1奇数X1费用1×1×22不可拆分返回2dfs(1,2)字符0X0直接返回flatCost1两段和3对比原值4更新res3返回3计算dfs(2,4)子串10逻辑同上返回3两段总和336对比初始res16更新res6dfs(0,4)最终返回6输出结果6和样例匹配。二、算法存在的性能缺陷针对原题数据范围1e5当前实现是纯暴力递归无记忆化缓存同一个区间[l,r)会被多次重复递归计算当字符串长度1e5时递归深度极高、重复计算爆炸会直接栈溢出超时仅能处理极小长度测试用例。三、时间复杂度 额外空间复杂度分两种场景1. 现有无记忆化暴力递归版本代码原生实现时间复杂度设字符串长度为n每次偶数区间都会分裂成两个等长子区间形成满二叉拆分树拆分树节点总数为 O(n)但无记忆缓存大量区间重复遍历最坏情况时间复杂度为O(2ⁿ)指数级仅n≤20可运行n1e5完全不可用。额外空间复杂度前缀和数组长度n1 → O(n)递归调用栈每次对半拆分栈最大深度 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,n1)fori,ch:ranges{sum[i1]sum[i]int(ch-0)}// 计算子串 [l, r) 的最小费用注意区间是左闭右开方便计算vardfsfunc(int,int)intdfsfunc(l,rint)int{x:sum[r]-sum[l]ifx0{returnflatCost}// 不拆分res:(r-l)*x*encCost// 拆分if(r-l)%20{m:(lr)/2resmin(res,dfs(l,m)dfs(m,r))}returnres}returnint64(dfs(0,n))}funcmain(){s:1010encCost:2flatCost:1result:minCost(s,encCost,flatCost)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defminCost(s:str,encCost:int,flatCost:int)-int:nlen(s)# 前缀和记录 1 的个数prefix_sum[0]*(n1)fori,chinenumerate(s):prefix_sum[i1]prefix_sum[i]int(ch)# 记忆化搜索避免重复计算memo{}defdfs(l:int,r:int)-int:# 子串为 [l, r)左闭右开if(l,r)inmemo:returnmemo[(l,r)]onesprefix_sum[r]-prefix_sum[l]zeros(r-l)-ones# 全是 0直接压平ifones0:memo[(l,r)]flatCostreturnflatCost# 不拆分按位编码res(r-l)*ones*encCost# 如果长度是偶数尝试拆分if(r-l)%20:mid(lr)//2resmin(res,dfs(l,mid)dfs(mid,r))memo[(l,r)]resreturnresreturndfs(0,n)defmain():s1010encCost2flatCost1resultminCost(s,encCost,flatCost)print(result)if__name____main__:main()C完整代码如下#includeiostream#includevector#includestring#includefunctional#includealgorithm#includeunordered_mapusingnamespacestd;longlongminCost(string s,intencCost,intflatCost){intns.length();vectorintprefix_sum(n1,0);// 构建前缀和for(inti0;in;i){prefix_sum[i1]prefix_sum[i](s[i]-0);}// 记忆化搜索使用字符串作为键存储状态unordered_mapstring,intmemo;// DFS函数functionint(int,int)dfs[](intl,intr)-int{// 生成状态键string keyto_string(l),to_string(r);if(memo.find(key)!memo.end()){returnmemo[key];}intonesprefix_sum[r]-prefix_sum[l];// 全是0直接压平if(ones0){memo[key]flatCost;returnflatCost;}// 不拆分按位编码intres(r-l)*ones*encCost;// 如果长度是偶数尝试拆分if((r-l)%20){intmid(lr)/2;resmin(res,dfs(l,mid)dfs(mid,r));}memo[key]res;returnres;};return(longlong)dfs(0,n);}intmain(){string s1010;intencCost2;intflatCost1;longlongresultminCost(s,encCost,flatCost);coutresultendl;return0;}