LeetCode 3864. 划分二进制字符串的最小费用 - Go 实现核心思路分治递归 前缀和gofunc minCost(s string, encCost int, flatCost int) int64 {n : len(s)// 前缀和数组pre[i] 表示 s[0..i-1] 中 1 的个数pre : make([]int, n1)for i : 1; i n; i {pre[i] pre[i-1]if s[i-1] 1 {pre[i]}}enc : int64(encCost)flat : int64(flatCost)var dfs func(l, r int) int64dfs func(l, r int) int64 {length : r - lx : pre[r] - pre[l] // 区间内 1 的个数// 不拆分的费用var res int64if x ! 0 {res int64(length) * int64(x) * enc} else {res flat}// 长度为偶数时可以拆分为两个等长子区间if length%2 0 {m : (l r) / 2splitCost : dfs(l, m) dfs(m, r)if splitCost res {res splitCost}}return res}return dfs(0, n)}算法详解步骤 说明前缀和 pre[i] 存储前 i 个字符中 1 的数量O(1) 查询任意区间 [l, r) 内敏感元素个数不拆分 X 0 → len * X * encCostX 0 → flatCost拆分 仅当区间长度为偶数时从中点 m (lr)/2 拆分为两个等长子区间递归求和取最小 对每个区间比较不拆分和拆分两种方案取费用较小者复杂度分析- 时间复杂度O(n)递归树类似线段树结构总节点数为 O(n)- 空间复杂度O(n)前缀和数组 递归栈深度示例验证输入s 1010, encCost 2, flatCost 1方案 计算 费用不拆分 L4, X2 → 4*2*216 16拆一次 10 10每个 L2, X1 → 2*1*24共 8 8拆到底 1(2) 0(1) 1(2) 0(1) 6 ✓输出6