题目描述
A binary string is monotone increasing if it consists of some number of 0’s (possibly none), followed by some number of 1’s (also possibly none).
You are given a binary string s. You can flip s[i] changing it from 0 to 1 or from 1 to 0.
Return the minimum number of flips to make s monotone increasing.
Example1:
Input: s = “00110” Output: 1 Explanation: We flip the last digit to get 00111.
Example2:
Input: s = “010110” Output: 2 Explanation: We flip to get 011111, or alternatively 000111.
Example3:
Input: s = “00011000” Output: 2 Explanation: We flip to get 00000000.
NOTE
- 1 <= S.length <= 20000
- S only consists of ‘0’ and ‘1’ characters.
解题思路
- 参考 > r
- 需要使用两个 dp 数组，其中 cnt1[i] 表示将范围是 [0, i-1] 的子串内最小的将1转为0的个数，从而形成单调字符串。同理，cnt0[j] 表示将范围是 [j, n-1] 的子串内最小的将0转为1的个数，从而形成单调字符串。
- 这样最终在某个位置使得 cnt0[i]+cnt1[i] 最小的时候，就是变为单调串的最优解，这样就可以完美的解决上面的例子，子串 “100” 的最优解是将1变为0，而后面的 “11111110010111011” 的最优解是将4个0变为1，总共加起来就是5
DP
class Solution {
public:
int minFlipsMonoIncr(string s) {
int size = s.size();
vector<int> cnt1(size, 0), cnt0(size, 0);
int res = INT_MAX;
for(int i = 1, j = size - 2; i < size, j >= 0; i++, j--){
cnt1[i] += cnt1[i - 1] + (s[i - 1] == '0' ? 0 : 1);
cnt0[j] += cnt0[j + 1] + (s[j + 1] == '1' ? 0 : 1);
}
for(int i = 0; i < size; i++){
res = min(res, cnt1[i] + cnt0[i]);
}
return res;
}
};
改进版本
