926. 将字符串翻转到单调递增

如果一个二进制字符串，是以一些 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'

单调递增的字符串满足以下性质：

• 首个字符是 0 或 1；
• 其余的每个字符，字符 0 前面的相邻字符一定是 0，字符 1 前面的相邻字符可以是 0 或 1。

方法一：动态规划

public int minFlipsMonoIncr2(String s) {
        int m = s.length();
        int[][] dp = new int[m + 1][2];
        for (int i = 1; i <= m; i++) {
            if (s.charAt(i - 1) == '0') {
                dp[i][0] = dp[i - 1][0];
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1] + 1);
            } else {
                dp[i][0] = dp[i - 1][0] + 1;
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]);
            }
        }
        return Math.min(dp[m][0], dp[m][1]);
    }

// 状态压缩
public  int minFlipsMonoIncr(String s) {
        int n = s.length();
        int dp0 = 0, dp1 = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            int dp0New = dp0, dp1New = Math.min(dp0, dp1);
            if (c == '1') {
                // 需要把1换成0，则 dp0New++
                dp0New++;
            } else {
                // 需要把0换成1，则 dp1New++
                dp1New++;
            }
            dp0 = dp0New;
            dp1 = dp1New;
        }
        return Math.min(dp0, dp1);
    }

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/flip-string-to-monotone-increasing
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。