解題說明
Flip String to Monotone Increasing
題目描述：
給定一個只包含 '0' 和 '1' 的二進位字串 s，你可以翻轉任意數量的字元（'0' 變 '1' 或 '1' 變 '0'）。求最少翻轉次數使字串變成單調遞增（所有 '0' 在所有 '1' 的左邊）。
解題思路： 前綴 1 計數法：
想像一條分界線，左邊全是 '0'，右邊全是 '1'。我們需要：
- 把分界線左邊的
'1'翻成'0' - 把分界線右邊的
'0'翻成'1'
用一個變數 ones 追蹤目前為止遇到的 '1' 的數量，用 flips 記錄最小翻轉次數：
遍歷字串，對每個字元：
- 若為
'1'：ones++（可能需要未來翻轉） - 若為
'0'：要麼翻這個'0'為'1'（flips + 1），要麼把之前所有'1'翻為'0'（ones）。取較小值：flips = min(flips + 1, ones)。
C++ 解法
複雜度分析
時間複雜度：O(n) — 一次遍歷字串。
空間複雜度：O(1) — 只使用兩個變數。
虛擬碼
1. Initialize ones = 0, flips = 0. 2. For each character c in s: a. If c == '1': increment ones. b. If c == '0': flips = min(flips + 1, ones). 3. Return flips.
其他解法
前綴和 + 枚舉分割點：O(n) 時間、O(n) 空間。先計算前綴 1 的數量和後綴 0 的數量，枚舉每個分割點取最小值。邏輯清晰但需要額外空間。
DP 雙狀態：O(n) 時間、O(1) 空間。定義 dp0 = 到目前為止以 '0' 結尾的最小翻轉數，dp1 = 以 '1' 結尾的最小翻轉數。轉移：dp0' = dp0 + (c == '1')，dp1' = min(dp0, dp1) + (c == '0')。最終答案 min(dp0, dp1)。
延伸思考
flips = min(flips + 1, ones)背後的直覺是什麼？為什麼只需要這兩個選項？- 如果字串包含三種字元（例如 '0', '1', '2'），要使其單調遞增，如何擴展此方法？
- 本題與「前綴和」有何關聯？如何用前綴和的方式理解最佳分割點？