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