如果一个二进制字符串，是以一些 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
