926. Flip String to Monotone Increasing
- Hardness: \(\color{orange}\textsf{Medium}\)
- Ralated Topics:
String、Dynamic Programming
一、題目
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 0 to 1 or from 1 to 0.
Return the minimum number of flips to make s monotone increasing.
Example 1:
- Input: s = “00110”
- Output: 1
- Explanation: We flip the last digit to get 00111.
Example 2:
- Input: s = “010110”
- Output: 2
- Explanation: We flip to get 011111, or alternatively 000111.
Example 3:
- Input: s = “00011000”
- Output: 2
- Explanation: We flip to get 00000000.
Constraints:
1 <= s.length <= 10^5s[i]is either'0'or'1'.
二、分析
- 這題可以使用動態規劃來解題，將
dp[0][i]訂為將s[i]翻成0可以符合題目需求的最少次數，dp[1][i]為將s[i]翻成1可以符合題目需求的最少次數。 - 當
s[i] == 0時，前者一定要是0；當s[i] == 1時，前者可以為0或1。 - 根據上述可以得到狀態轉移方程式為：
if (s[i] == '1') {
dp[0][i] = dp[0][i-1] + 1;
dp[1][i] = min(dp[0][i-1], dp[1][i-1]);
} else {
dp[0][i] = dp[0][i-1];
dp[1][i] = min(dp[0][i-1], dp[1][i-1]) + 1;
}三、解題
1. DP
- Time complexity: \(O(n)\)
- Space complexity: \(O(n)\)
int minFlipsMonoIncr(string s) {
int n = s.length();
vector<vector<int>> dp(2, vector<int>(n, 0));
if (s[0] == '0')
dp[1][0] = 1;
else
dp[0][0] = 1;
for (int i = 1; i < n; i++) {
if (s[i] == '1') {
dp[0][i] = dp[0][i-1] + 1; // 將 1 翻成 0
dp[1][i] = min(dp[0][i-1], dp[1][i-1]);
} else {
dp[0][i] = dp[0][i-1];
dp[1][i] = min(dp[0][i-1], dp[1][i-1]) + 1; // 將 0 翻成 1
}
}
return min(dp[0][n-1], dp[1][n-1]);
}1. DP(space optimized)
- 從狀態轉移方程式觀察，可發現只與「前一狀態」相關，故可以進行狀態壓縮
- Time complexity: \(O(n)\)
- Space complexity: \(O(1)\)
int minFlipsMonoIncr(string s) {
int n = s.length();
int zero = 0;
int one = 0;
if (s[0] == '0')
one = 1;
else
zero = 1;
for (int i = 1; i < n; i++) {
if (s[i] == '1') {
one = min(zero, one);
zero++;
} else {
one = min(zero, one) + 1;
}
}
return min(zero, one);
}