Q4. Minimum Cost to Partition a Binary String

📘 題目敘述

給你二進位字串 s、encCost、flatCost。每段 segment 依是否含有 '1' 計算成本，且只有偶數長度 segment 可切成兩段連續等長 segment。請求最小總成本。

條件限制

• 1 <= s.length <= 10^5
• 1 <= encCost, flatCost <= 10^5

🧠 解題思路

核心是遞迴 dfs(l, r)，回傳區間 [l, r) 的最小成本。先以 countone(l, r) 計算此段 '1' 數量，再比較「不切分」與「可切半時切分」兩者最小值。

所有變數

• f：flatCost
• e：encCost
• one：區間內 '1' 數量
• i：整段不切分成本

🪜 主要流程步驟

1. 由整段啟動 dfs

minCost 先存成本參數，再呼叫 dfs(0, s.size(), s)。

2. countone 分治計算 1 的數量

單點直接判斷，否則切半遞迴加總。

3. dfs 做決策

• one == 0：回傳 flatCost
• one > 0：先算整段成本，若長度偶數可再比較切半總和

⏱️ 複雜度

• 時間複雜度：O(n log^2 n)
• 空間複雜度：O(log n)

💻 程式碼實作

class Solution {
public:
    int f;
    int e;
    int countone(int l, int r, string& s) {
        if (l + 1 == r) {
            if (s[l] == '1') {
                return 1;
            }
            return 0;
        }
        int m = (l + r) / 2;
        return countone(l, m, s) + countone(m, r, s);
    }
    long long dfs(int l, int r, string& s) {
        int one = countone(l, r, s);
        if (one == 0) {
            return f;
        }
        if ((r - l) % 2 == 0) {
            long long i = 1LL * (r - l) * one * e;
            return min(i, dfs(l, (l + r) / 2, s) + dfs((l + r) / 2, r, s));
        }
        return 1LL * (r - l) * one * e;
    }
    long long minCost(string s, int encCost, int flatCost) {
        f = flatCost;
        e = encCost;
        return dfs(0, s.size(), s);
    }
};

🔗 題目連結

https://leetcode.com/contest/weekly-contest-492/problems/minimum-cost-to-partition-a-binary-string/