動機

做完有種我不會dp的感覺

Problem

A binary string is monotone increasing if it consists of some number of 0's (possibly none), followed by some number of 1's (also possibly none).

You are given a binary string s. You can flip s[i] changing it from 0 to 1 or from 1 to 0.

Return the minimum number of flips to make s monotone increasing.

 

Example 1:

Input: s = "00110"Output: 1Explanation: We flip the last digit to get 00111.

Example 2:

Input: s = "010110"Output: 2Explanation: We flip to get 011111, or alternatively 000111.

Example 3:

Input: s = "00011000"Output: 2Explanation: We flip to get 00000000.

 

Constraints:

    t
  • 1 <= s.length <= 105
    • t
  • s[i] is either '0' or '1'.

Sol

原本是用divide and conquer去數

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        @cache
        def one(i,j):
            if j<=i:
                return 0
            elif j-i == 1:
                return 0 if s[i:j] == "1" else 1
            else:
                mid = (i+j)//2
                return one(i,mid)+one(mid,mid+1)+one(mid+1,j)
        @cache
        def zero(i,j):
            if j<=i:
                return 0
            elif j-i == 1:
                return 1 if s[i:j] == "1" else 0
            else:
                mid = (i+j)//2
                return zero(i,mid)+zero(mid,mid+1)+zero(mid+1,j)
        return min([zero(0,k)+one(k,len(s)) for k in range(0,len(s)+1)])

但zero與one是互斥的，所以可以用一邊推出另一邊 但這樣還是n^2 log n

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        @cache
        def zero(i,j):
            if j<=i:
                return 0
            elif j-i == 1:
                return 0 if s[i:j] == "1" else 1
            else:
                mid = (i+j)//2
                return zero(i,mid)+zero(mid,mid+1)+zero(mid+1,j)
        @cache
        def one(i,j):
            return (j-i)-zero(i,j)
        
        return min([zero(0,k)+one(k,len(s)) for k in range(0,len(s)+1)])

怎麼快速算出one的數目? 或是說，one的總和? prefix sum

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        ones = [0]
        for c in s:
            ones.append(ones[-1]+(1 if c == "1" else 0))
        @cache
        def zero(i,j):
            return ones[j]-ones[i]
        @cache
        def one(i,j):
            return (j-i)-zero(i,j)
        
        return min([zero(0,k)+one(k,len(s)) for k in range(0,len(s)+1)])

另外只看最後一位會發現如果是1，可以直接接上去

如果是0，不是把前面的1換成0，就是把自己這一位換成1，所以有下面的dp

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        ones = 0
        dp = 0
        for c in s:
            if c == "0":
                dp = min(dp+1,ones) # 0 to 1, all 1 to 0
            else:
                ones += 1 # append to the tail
        return dp