LeetCode-926 将字符串翻转到单调递增

题目描述

如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 1）的形式组成的，那么该字符串是 单调递增 的。

给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0 。

返回使 s 单调递增的最小翻转次数。

示例 1：

输入：s = "00110"
输出：1
解释：翻转最后一位得到 00111.

示例 2：

输入：s = "010110"
输出：2
解释：翻转得到 011111，或者是 000111。

示例 3：

输入：s = "00011000"
输出：2
解释：翻转得到 00000000。

提示：

• 1 <= s.length <= 105
• s[i] 为 '0' 或 '1'

题解-动态规划

根据前一位是0或1递推计算开销，后一步的开销由前一步决定，马尔科夫过程。

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        pre0, pre1 = 0, 0 # 前1位为0或1的开销
        for ch in s:
            if ch == '0':
                pre1 = min(pre0, pre1) + 1
            else:
                pre1 = min(pre0, pre1)
                pre0 = pre0 + 1
        return min(pre0, pre1)

时间复杂度O(n)空间复杂度O(1)