原贴地址：https://dawnmagnet.github.io/algorithm-station/docs/2022/6/11

如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 1）的形式组成的，那么该字符串是 单调递增 的。

给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0 。

返回使 s 单调递增的最小翻转次数。

示例 1：

输入：s = “00110” 输出：1 解释：翻转最后一位得到 00111.

示例 2：

输入：s = “010110” 输出：2 解释：翻转得到 011111，或者是 000111。

示例 3：

输入：s = “00011000” 输出：2 解释：翻转得到 00000000。 提示：

1 <= s.length <= 105 s[i] 为 ‘0’ 或 ‘1’ 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/flip-string-to-monotone-increasing 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析 - 1

#

首先理解一下题目，主要的难点是翻转次数。其实有一个关键的要点，只需在字符串中选择一个确切的位置，作为0和1的分界线，那么就可以很快地计算得到整个字符串变成有序的翻转次数。选定了一个分界线之后，将其之前的“1”全部变成“0”，将其之后的“0”全部变成“1”。就可以很快地得到翻转所需的次数。

所以问题变成了，如何快速地求一个特定的分界线，前面的“1”的个数和后面的“0”的个数呢？我首先想到的是动态规划，使用两个数组，分别从数组的两个方向进行遍历，可以很轻松地得到每个特定位置前面的“1”的个数和后面的“0”的个数。最后遍历一遍，分别获得每个特定位置上前面的“1”的个数和后面的“0”的个数之和，并求那个位置是一个开销最小的位置（也就是前面的“1”的个数和后面的“0”的个数之和最小）。返回这个答案即可

C++ 代码 - 1

#

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int n = s.size();
        vector<int> v1(n + 1), v2(n + 1);
        for (int i = 0; i < n; ++i) v1[i + 1] = v1[i] + (s[i] == '1');
        for (int i = n - 1; i >= 0; --i) v2[i] = v2[i + 1] + (s[i] == '0');
        int res = n;
        for (int i = 0; i <= n; ++i)
            res = min(res, v1[i] + v2[i]);
        return res;
    }
};

思路分析 2

#

上面的这种思路还有一些可以优化的地方。因为使用了过量的空间，开了两个数组。在这里可以使用一种新的方法，从而能在仅占用 O(1)空间的情况下做出这道题。

换一个思路进行思考，动态规划的思路。如果我们已知一个字符串，它的最小翻转次数是 n。那么在其之后新加一个字符，能否计算这个新的字符串的最小翻转次数呢？

如果新加的字符是1，那么它前面是0或者1都是合理的，不需要新添加翻转次数。

如果新加的字符是0，那么它前面必须是字符0，也不需要增加翻转次数。

因为考虑到每次翻转之后，跟前一个字符串的最后一个字符有很大的关系，所以必须分开讨论

首先假设 dp[i][j]是一个动态规划数组，它的含义是对于 s的子字符串 s[0:i]，如果在翻转之后最后一位是 j(j是0或1)的最小翻转次数是多少。

首先可以假设以下推导式

• 如果新添加的字符是 0，那么 dp[i][0]=dp[i-1][0]
• 如果新添加的字符是 1，那么 dp[i][1]=min(dp[i-1][0], dp[i-1][1])

以上两种情况是比较好想到的，但如果新添加的字符也是需要翻转的呢？那就需要多加一个翻转次数 1

• 如果新添加的字符是 0，那么 dp[i][1]=min(dp[i-1][0], dp[i-1][1])+1
• 如果新添加的字符是 1，那么 dp[i][0]=dp[i-1][0]+1

以上就完成了一个逻辑自洽的动态规划状态转移方程。

C++代码 - 2

#

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int a = 0, b = 0;
        for (auto & ch : s) {
            b = min(a, b);
            if (ch == '1') a++;
            else b++;
        }
        return min(a, b);
    }
};