Problem
A string of '0's and '1's is monotone increasing if it consists of some number of '0's (possibly 0), followed by some number of '1's (also possibly 0.)
We are given a string S of '0's and '1's, and we may flip any '0' to a '1' or a '1' to a '0'.
Return the minimum number of flips to make S monotone increasing.
Example 1:
Input: "00110" Output: 1 Explanation: We flip the last digit to get 00111.
Example 2:
Input: "010110" Output: 2 Explanation: We flip to get 011111, or alternatively 000111.
Example 3:
Input: "00011000" Output: 2 Explanation: We flip to get 00000000.
Note:
1 <= S.length <= 20000Sonly consists of'0'and'1'characters.
Solution: DP
l[i] := number of flips to make S[0] ~ S[i] become all 0s.
r[i] := number of flips to make S[i] ~ S[n – 1] become all 1s.
Try all possible break point, S[0] ~ S[i – 1] are all 0s and S[i] ~ S[n-1] are all 1s.
ans = min{l[i – 1] + r[i]}
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: int minFlipsMonoIncr(string S) { const int n = S.size(); vector<int> l(n + 1); // 1 -> 0 vector<int> r(n + 1); // 0 -> 1 l[0] = S[0] - '0'; r[n - 1] = '1' - S[n - 1]; for (int i = 1; i < n; ++i) l[i] = l[i - 1] + S[i] - '0'; for (int i = n - 2; i >= 0; --i) r[i] = r[i + 1] + '1' - S[i]; int ans = r[0]; // all 1s. for (int i = 1; i <= n; ++i) ans = min(ans, l[i - 1] + r[i]); return ans; } }; |
C++ v2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua class Solution { public: int minFlipsMonoIncr(string S) { const int n = S.length(); vector<vector<int>> dp(n + 1, vector<int>(2)); for (int i = 1; i <= n; ++i) { if (S[i - 1] == '0') { dp[i][0] = dp[i - 1][0]; dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + 1; } else { dp[i][0] = dp[i - 1][0] + 1; dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]); } } return min(dp[n][0], dp[n][1]); } }; |
C++ v2 / O(1) Space
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: int minFlipsMonoIncr(string S) { const int n = S.length(); int dp0 = 0; int dp1 = 0; for (int i = 1; i <= n; ++i) { int tmp0 = dp0 + (S[i - 1] == '1'); dp1 = min(dp0, dp1) + (S[i - 1] == '0'); dp0 = tmp0; } return min(dp0, dp1); } }; |