personal blog: http://fuxuemingzhu.cn/

directory

Prefix calculates dynamic programming. The Prefix calculates dynamic programming

Reference Date

Title address: https://leetcode.com/problems/flip-string-to-monotone-increasing/description/

Topic describes

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 < = S.length < = 20000S only strings of ‘0’ and ‘1’ characters.

Subject to

A string has a 0 and a 1. Ask at least how many characters to flip to make the string program a monotonically increasing string.

The problem solving method

The Prefix calculation

The second problem of the week, this problem is still a little difficult to think about.

As a general rule, we use the Prefix array to store how many 1s precede each location. Because our ultimate goal is to become a string with a 0 and a 1 in front of it, so we can go through the array, and we’re going to go through all the positions that we’re going through, and we’re going to have to count how many ones we have in front of each position plus how many zeros we have after each position. Because the first 1 has to be flipped to 0, and the second 0 has to be flipped to 1.

Anyway, you just have to figure out how many ones are in front of each position, and then, again, you have to minimize the sum of the ones in front of each position and the zeros after each position.

The P array is used to hold the first 1 of each position. So the number of zeros is going to be the total number of zeros (that is, the total number minus the total number of ones) minus the number of zeros (that is, the current position index minus the number of ones).

It’s order N in time, order N in space.

```
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)))
```

Dynamic programming

The master on the other side of the station came up with the method, I feel inferior ah, look for a long time to consult to be able to figure it out reluctantly.

This is a bit like buying and selling stocks, both using a two-dimensional dp array that holds the minimum number of times a string ending in 0 or 1 needs to be flipped.

For convenience, I’ve added a space to the DP array, which means that I don’t have to do any flipping before the first string has even started.

So, when we traverse to the I position of the string:

- if the character in this position is

`'0'`

, then: The current dp array ending in 0 is equal to the previous DP ending in 0, that is, there is no need to do any operation, at this time, the previous dp must end in 0; The current dp array ending in 1 is equal to Min(the previous dp + 1 ending in 0, the previous DP + 1). The idea here is that there’s a situation where you end up with the previous 0 and you flip the current 0 to 1; The other case is if the previous digit ends in a 1 and the current 0 is flipped to a 1. We need to minimize these two cases. You can end it with either a 0 or a 1.

- if the character in this position is

`'1'`

, then: The current dp array ending in 0 is equal to the previous DP ending in 0 + 1, that is, the current 1 is flipped to 0, at this time, the previous one can only end in 0; The current dp array ending in 1 is equal to `Min(dp ending in 0, dp ending in 1)`

. So what that means is how many times do I have to flip this position over to end in 1?Of course, it’s the minimum number of times you can flip a 0 or a 1, because you don’t have to flip the 1, but you can flip the 1 anyway. You can end it with either a 0 or a 1.

To sum up, it is important to understand that dp array is the number of states ending in this second dimension number. For example, DP [I][0] is the number of states that need to be flipped if the ith number ends in 0. And then, the thing to understand is that if we’re traversing this character there’s no limit to whether we’re going to flip it or not, so whether we flip it or not we have to take into account how the DP is going to update when this position becomes either 1 or 0. The way to update is to look at the previous state, the previous state to the current state, what you need to do, and how many flips you have.

It’s order N in time, order N in space.

```
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])
```

Obviously, in the above approach, each DP shift is only related to the previous state, so you can optimize the spatial complexity to O(1). The code is as follows:

```
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])
```

The resources

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

The date of

October 21, 2018 — This week’s race is a bit difficult

### Read More:

- PCIe Lane flip and PN flip (Lane reverse and polarity)
- ThinkPad T400 fan error error report: an example of solving non fan problem
- Solve the problem of unable to locate package python3.6 when upgrading from python3.5 to python3.6 in ubantu16.04
- Error lnk1123: failure during conversion to coff: problem solving
- Call to undefined function oci_ Connect() problem solving
- “Failed to load session” Ubuntu “problem solving summary
- Leetcode 832. Flip image
- String index out of range: 100 error report details and Solutions
- Failed to connect to 127.0.0.1 port 43571: problem solving record
- mysql problem solving: mysqladmin: connect to server at’localhost’ failed
- Problem solving: failed to connect to github.com port 443: Operation timed out（2020.06.04）
- After introducing sass into Vue project, start to report error typeerror [err]_ INVALID_ ARG_ Type]: the “path” argument must be of type string
- Problem solving: PDF cannot be opened, and acrobat failed to connect to a DDE server appears
- Problem solving of failed to read candidate component class in Java
- Python conversion hex to string, high and low data processing
- A repeated string is composed of two identical strings. For example, abcabc is a repeated string with length of 6, while abcba does not have a duplicate string. Given any string, please help Xiaoqiang find the longest repeated substring.
- Failed to load resource: net::ERR_ INSECURE_ Response problem solving record
- VirtualBox problem solving set -[drm:vmw_host_log [vmwgfx]] *ERROR* Failed to send host log message
- How to solve the problem of string to CString garbled code?
- Duplicate class com.xxx.xxx Find in modules problem solving (Aidl interdependence problem)