# 926. Flip String to Monotone Increasing 将字符串翻转到单调递增

@TOC

## # 题目描述

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

We are given a string S of `'0'`s and `'1'`s, and we may flip any `'0'` to a `'1'` or a `'1'` to a `'0'`.

Return the minimum number of flips to make `S` monotone increasing.

Example 1:

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

Example 2:

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

Example 3:

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

Note:

1. 1 <= S.length <= 20000
2. S only consists of '0' and '1' characters.

## # 解题方法

### # Prefix计算

``````class Solution(object):
def minFlipsMonoIncr(self, S):
"""
:type S: str
:rtype: int
"""
N = len(S)
P = [0] # how many ones
res = float('inf')
for s in S:
P.append(P[-1] + int(s))
return min(P[i] + (N - P[-1]) - (i - P[i]) for i in range(len(P)))
``````

### # 动态规划

1. 如果这个位置的字符是`'0'`，那么：
• 当前以0结尾的dp数组等于前面的以0结尾的dp，即不需要做任何操作，此时前面必须是0结尾;
• 当前以1结尾的dp数组等于Min(前面的以0结尾的dp + 1，前面的以1结尾的dp + 1)。这里的含义是一种情况为前面的0到前面的那个位置结束，把当前的0翻转成1；另一种情况是前面一位以1结束不变，把当前的0翻转成1。需要求这两个情况的最小值。此时前面可以以0或者1结尾。
1. 如果这个位置的字符是`'1'`，那么：
• 当前以0结尾的dp数组等于前面的以0结尾的dp + 1，即把当前的1翻转成0，此时前面只能以0结尾；
• 当前以1结尾的dp数组等于`Min(前面的以0结尾的dp，前面的以1结尾的dp)`。这里的含义是该位置以1结尾需要翻转多少次呢？当然是前面翻转0或者1的次数最小值，因为当前的1一定不用翻转，而前面无论怎么翻转都能满足条件。此时前面可以以0或者1结尾。

``````class Solution(object):
def minFlipsMonoIncr(self, S):
"""
:type S: str
:rtype: int
"""
N = len(S)
dp = [[0] * 2 for _ in range(N + 1)]
for i in range(1, N + 1):
if S[i - 1] == '0':
dp[i][0] = dp[i - 1][0]
dp[i][1] = min(dp[i - 1][1], dp[i - 1][0]) + 1
else:
dp[i][0] = dp[i - 1][0] + 1
dp[i][1] = min(dp[i - 1][1], dp[i - 1][0])
return min(dp[N][0], dp[N][1])
``````

``````class Solution(object):
def minFlipsMonoIncr(self, S):
"""
:type S: str
:rtype: int
"""
N = len(S)
dp = [0] * 2
for i in range(1, N + 1):
if S[i - 1] == '0':
dp[0] = dp[0]
dp[1] = min(dp[1], dp[0]) + 1
else:
dp[1] = min(dp[1], dp[0])
dp[0] = dp[0] + 1
return min(dp[0], dp[1])
``````

## # 参考资料

https://leetcode.com/problems/flip-string-to-monotone-increasing/discuss/183859/Java-DP-using-O(N)-time-and-O(1)-space

## # 日期

2018 年 10 月 21 日 —— 这个周赛有点难