0926-flip-string-to-monotone-increasing.adoc

926. Flip String to Monotone Increasing

{leetcode}/problems/flip-string-to-monotone-increasing/[LeetCode - Flip String to Monotone Increasing^]

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. 1 ⇐ S.length ⇐ 20000

2. S only consists of '0' and '1' characters.

思路分析

如果下标 i 处的字符是 0，则只有当下标 i−1 处的字符是 0 时才符合单调递增；如果下标 i 处的字符是 1，则下标 i−1 处的字符是 0 或 1 都符合单调递增，此时为了将翻转次数最小化，应分别考虑下标 i−1 处的字符是 0 和 1 的情况下需要的翻转次数，取两者的最小值。

对于 0≤i<n，用 dp[i][0] 和 dp[i][1] 分别表示下标 i 处的字符为 0 和 1 的情况下使得 s[0..i] 单调递增的最小翻转次数。

一刷

link:{sourcedir}/_0926_FlipStringToMonotoneIncreasing.java[role=include]

参考资料

1. 926. 将字符串翻转到单调递增 - 官方题解