926. Flip String to Monotone Increasing - Explanation

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        dp = {}

        def dfs(i, mono):
            if (i, mono) in dp:
                return dp[(i, mono)]
            if i == len(s):
                return 0

            if mono and s[i] == "0":
                dp[(i, mono)] = min(1 + dfs(i + 1, False), dfs(i + 1, mono))
            elif mono and s[i] == "1":
                dp[(i, mono)] = min(1 + dfs(i + 1, mono), dfs(i + 1, False))
            elif not mono and s[i] == "1":
                dp[(i, mono)] = dfs(i + 1, mono)
            else:
                dp[(i, mono)] = 1 + dfs(i + 1, mono)

            return dp[(i, mono)]

        return dfs(0, True)

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        n = len(s)
        dp = [[0] * 2 for _ in range(n + 1)]

        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                dp[i][1] = min(1 + dp[i + 1][0], dp[i + 1][1])
                dp[i][0] = 1 + dp[i + 1][0]
            else:  # s[i] == '1'
                dp[i][1] = min(1 + dp[i + 1][1], dp[i + 1][0])
                dp[i][0] = dp[i + 1][0]

        return dp[0][1]

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        n = len(s)
        dp = [0, 0]

        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                new_dp_1 = min(1 + dp[0], dp[1])
                new_dp_0 = dp[0] + 1
            else:  # s[i] == '1'
                new_dp_1 = min(dp[1] + 1, dp[0])
                new_dp_0 = dp[0]

            dp[1] = new_dp_1
            dp[0] = new_dp_0

        return dp[1]

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        n = len(s)
        left_ones = [0] * (n + 1)
        right_zeros = [0] * (n + 1)

        for i in range(n):
            left_ones[i + 1] = left_ones[i] + (1 if s[i] == '1' else 0)

        for i in range(n - 1, -1, -1):
            right_zeros[i] = right_zeros[i + 1] + (1 if s[i] == '0' else 0)

        res = float('inf')
        for i in range(n + 1):
            res = min(res, left_ones[i] + right_zeros[i])

        return res

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        res  = cntOne = 0
        for c in s:
            if c == '1':
                cntOne += 1
            else:
                res = min(res + 1, cntOne)
        return res