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

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完整代码如下：

package main

 import (
    "fmt"
)

 func minCost(s string, encCost, flatCost int)int64 {
    n := len(s)
    sum := make([]int, n+1)
    for i, ch := range s {
        sum[i+1] = sum[i] + int(ch-'0')
    }

     // 计算子串 [l, r) 的最小费用，注意区间是左闭右开，方便计算
    var dfs func(int, int)int
    dfs = func(l, r int)int {
        x := sum[r] - sum[l]
        if x == 0 {
            return flatCost
        }

         // 不拆分
        res := (r - l) * x * encCost

         // 拆分
        if (r-l)%2 == 0 {
            m := (l + r) / 2
            res = min(res, dfs(l, m)+dfs(m, r))
        }

         return res
    }
    returnint64(dfs(0, n))
}

 func main() {
    s := "1010"
    encCost := 2
    flatCost := 1
    result := minCost(s, encCost, flatCost)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def minCost(s: str, encCost: int, flatCost: int) -> int:
    n = len(s)
    # 前缀和，记录 '1' 的个数
    prefix_sum = [0] * (n + 1)
    for i, ch in enumerate(s):
        prefix_sum[i + 1] = prefix_sum[i] + int(ch)

     # 记忆化搜索，避免重复计算
    memo = {}

     def dfs(l: int, r: int) -> int:
        # 子串为 [l, r)，左闭右开
        if (l, r) in memo:
            return memo[(l, r)]

         ones = prefix_sum[r] - prefix_sum[l]
        zeros = (r - l) - ones

         # 全是 0，直接压平
        if ones == 0:
            memo[(l, r)] = flatCost
            return flatCost

         # 不拆分：按位编码
        res = (r - l) * ones * encCost

         # 如果长度是偶数，尝试拆分
        if (r - l) % 2 == 0:
            mid = (l + r) // 2
            res = min(res, dfs(l, mid) + dfs(mid, r))

         memo[(l, r)] = res
        return res

     return dfs(0, n)

 def main():
    s = "1010"
    encCost = 2
    flatCost = 1
    result = minCost(s, encCost, flatCost)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  

  

    


 using namespace std;

 long long minCost(string s, int encCost, int flatCost) {
    int n = s.length();
    vector prefix_sum(n + 1, 0);

     // 构建前缀和
    for (int i = 0; i < n; i++) {
        prefix_sum[i + 1] = prefix_sum[i] + (s[i] - '0');
    }

     // 记忆化搜索，使用字符串作为键存储状态
    unordered_map memo;

     // DFS函数
    function dfs = [&](int l, int r) -> int {
        // 生成状态键
        string key = to_string(l) + "," + to_string(r);
        if (memo.find(key) != memo.end()) {
            return memo[key];
        }

         int ones = prefix_sum[r] - prefix_sum[l];

         // 全是0，直接压平
        if (ones == 0) {
            memo[key] = flatCost;
            return flatCost;
        }

         // 不拆分：按位编码
        int res = (r - l) * ones * encCost;

         // 如果长度是偶数，尝试拆分
        if ((r - l) % 2 == 0) {
            int mid = (l + r) / 2;
            res = min(res, dfs(l, mid) + dfs(mid, r));
        }

         memo[key] = res;
        return res;
    };

     return (long long)dfs(0, n);
}

 int main() {
    string s = "1010";
    int encCost = 2;
    int flatCost = 1;
    long long result = minCost(s, encCost, flatCost);
    cout << result << endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。