如果一個二進制字符串味滞，是以一些 0（可能沒有 0）后面跟著一些 1（也可能沒有 1）的形式組成的熄求，那么該字符串是 單調(diào)遞增 的次兆。
給你一個二進制字符串 s箱舞，你可以將任何 0 翻轉(zhuǎn)為 1 或者將 1 翻轉(zhuǎn)為 0 贮折。
返回使 s 單調(diào)遞增的最小翻轉(zhuǎn)次數(shù)裤翩。
示例 1：
輸入：s = "00110"
輸出：1
解釋：翻轉(zhuǎn)最后一位得到 00111.
示例 2：
輸入：s = "010110"
輸出：2
解釋：翻轉(zhuǎn)得到 011111，或者是 000111调榄。
示例 3：
輸入：s = "00011000"
輸出：2
解釋：翻轉(zhuǎn)得到 00000000踊赠。
提示：
- 1 <= s.length <= 105
- s[i] 為 '0' 或 '1'
單調(diào)遞增的字符串滿足以下性質(zhì)：
- 首個字符是 0 或 1；
- 其余的每個字符每庆，字符 0 前面的相鄰字符一定是 0筐带，字符 1 前面的相鄰字符可以是 0 或 1。
方法一：動態(tài)規(guī)劃
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]);
}
// 狀態(tài)壓縮
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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)腮出，非商業(yè)轉(zhuǎn)載請注明出處帖鸦。
