Hard

题目描述

给你一个二进制字符串 s 和两个整数 encCost 和 flatCost。

对于每个索引 i，s[i] = '1' 表示第 i 个元素是敏感的，s[i] = '0' 表示它不是敏感的。

字符串必须被分割成若干段。最初，整个字符串形成一个段。

对于长度为 L 且包含 X 个敏感元素的段：

  • 如果 X = 0，成本为 flatCost
  • 如果 X > 0，成本为 L * X * encCost

如果一个段的长度是偶数，你可以将其分割成两个长度相等的连续段，这种分割的成本是结果段的成本之和。

返回所有有效分割中可能的最小总成本。

示例 1：

输入：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 * 2 = 2，包含 "0" 的段成本为 flatCost = 1
- 总成本为 2 + 1 + 2 + 1 = 6，这是最小可能总成本

示例 2：

输入：s = "1010", encCost = 3, flatCost = 10
输出：12

示例 3：

输入：s = "00", encCost = 1, flatCost = 2
输出：2

约束条件：

  • 1 <= s.length <= 10^5
  • s 仅由 ‘0’ 和 ‘1’ 组成
  • 1 <= encCost, flatCost <= 10^5

解题思路

这道题是一个经典的分治问题，核心思想是对于每个段，我们需要决定是保持原样还是继续分割。

解题思路：

  1. 分治策略：对于任意一个段 [left, right]，我们有两种选择：

    • 不分割：直接计算该段的成本
    • 分割：如果长度为偶数，可以从中点分割成两个相等长度的子段

  2. 成本计算：

    • 如果段内没有敏感元素（‘1’），成本为 flatCost
    • 如果有敏感元素，成本为 长度 × 敏感元素数量 × encCost

  3. 优化技巧：

    • 使用前缀和快速计算任意区间内 ‘1’ 的数量
    • 使用记忆化搜索避免重复计算相同的子问题
    • 只有长度为偶数的段才能分割

  4. 递归过程：

    • 计算不分割的成本
    • 如果长度为偶数，计算分割后的成本
    • 返回两者中的最小值

推荐解法：记忆化递归 + 前缀和优化，时间复杂度优秀且代码清晰易懂。

代码实现

class Solution {
public:
    long long minCost(string s, int encCost, int flatCost) {
        int n = s.length();
        vector<int> prefix(n + 1, 0);
        
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + (s[i] == '1' ? 1 : 0);
        }
        
        unordered_map<string, long long> memo;
        
        function<long long(int, int)> solve = [&](int left, int right) -> long long {
            string key = to_string(left) + "," + to_string(right);
            if (memo.count(key)) return memo[key];
            
            int length = right - left + 1;
            int ones = prefix[right + 1] - prefix[left];
            
            // 不分割的成本
            long long noCost = (ones == 0) ? flatCost : (long long)length * ones * encCost;
            
            // 如果长度为偶数，尝试分割
            if (length % 2 == 0) {
                int mid = left + length / 2 - 1;
                long long splitCost = solve(left, mid) + solve(mid + 1, right);
                noCost = min(noCost, splitCost);
            }
            
            return memo[key] = noCost;
        };
        
        return solve(0, n - 1);
    }
};

class Solution:
    def minCost(self, s: str, encCost: int, flatCost: int) -> int:
        n = len(s)
        prefix = [0] * (n + 1)
        
        # 计算前缀和
        for i in range(n):
            prefix[i + 1] = prefix[i] + (1 if s[i] == '1' else 0)
        
        memo = {}
        
        def solve(left, right):
            if (left, right) in memo:
                return memo[(left, right)]
            
            length = right - left + 1
            ones = prefix[right + 1] - prefix[left]
            
            # 不分割的成本
            no_cost = flatCost if ones == 0 else length * ones * encCost
            
            # 如果长度为偶数，尝试分割
            if length % 2 == 0:
                mid = left + length // 2 - 1
                split_cost = solve(left, mid) + solve(mid + 1, right)
                no_cost = min(no_cost, split_cost)
            
            memo[(left, right)] = no_cost
            return no_cost
        
        return solve(0, n - 1)

public class Solution {
    private Dictionary<string, long> memo;
    private int[] prefix;
    private int encCost, flatCost;
    
    public long MinCost(string s, int encCost, int flatCost) {
        int n = s.Length;
        this.encCost = encCost;
        this.flatCost = flatCost;
        memo = new Dictionary<string, long>();
        prefix = new int[n + 1];
        
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + (s[i] == '1' ? 1 : 0);
        }
        
        return Solve(0, n - 1);
    }
    
    private long Solve(int left, int right) {
        string key = left + "," + right;
        if (memo.ContainsKey(key)) return memo[key];
        
        int length = right - left + 1;
        int ones = prefix[right + 1] - prefix[left];
        
        // 不分割的成本
        long noCost = (ones == 0) ? flatCost : (long)length * ones * encCost;
        
        // 如果长度为偶数，尝试分割
        if (length % 2 == 0) {
            int mid = left + length / 2 - 1;
            long splitCost = Solve(left, mid) + Solve(mid + 1, right);
            noCost = Math.Min(noCost, splitCost);
        }
        
        memo[key] = noCost;
        return noCost;
    }
}

var minCost = function(s, encCost, flatCost) {
    const n = s.length;
    const prefix = new Array(n + 1).fill(0);
    
    // 计算前缀和
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)每个子问题最多被计算一次，总共有O(n log n)个不同的子问题
空间复杂度O(n log n)记忆化存储和递归调用栈的空间开销