将字符串翻转到单调递增
我们先来看题目描述：
如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 1）的形式组成的，那么该字符串是 单调递增 的。
给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0 。
返回使 s 单调递增的最小翻转次数。
示例 1 ：
输入：s = "00110" 输出：1 解释：翻转最后一位得到 00111.示例 2 ：
输入：s = "010110" 输出：2 解释：翻转得到 011111，或者是 000111。示例 3 ：
输入：s = "00011000" 输出：2 解释：翻转得到 00000000。提示：
- 1 <= s.length <= 10*5
- s [i] 为 '0' 或 '1'
解决方案：动态规划
单调递增的字符串满足以下性质：
- 首个字符是 0 或 1；
- 其余的每个字符，字符 0 前面的相邻字符一定是 0，字符 1 前面的相邻字符可以是 0 或 1。
当 i>0 时，如果字符串 s 的长度为 i 的前缀即 s[0..i−1] 单调递增，且 s[i] 和 s[i−1] 也满足上述单调递增的顺序，则长度为 i+1 的前缀 s[0..i] 也单调递增。因此可以使用动态规划计算使字符串 s 单调递增的最小翻转次数。
由于字符串 s 的每个位置的字符可以是 0 或 1，因此对于每个位置需要分别计算该位置的字符是 0 和该位置的字符是 1 的情况下的最小翻转次数。
假设字符串 s 的长度是 n，对于 0≤i<n，用 dp[i][0] 和 dp[i][1] 分别表示下标 i 处的字符为 0 和 1 的情况下使得 s[0..i] 单调递增的最小翻转次数。
当 i=0 时，对应长度为 1 的前缀，一定满足单调递增，因此 dp[0][0] 和 dp[0][1] 的值取决于字符 s[i]。
具体而言，dp[0][0]=II(s[0]=‘1’)，dp[0][1]=II(s[0]=‘0’)，其中 II 为示性函数，当事件成立时示性函数值为 1，当事件不成立时示性函数值为 0。
当 1≤i<n 时，考虑下标 i 处的字符。如果下标 i 处的字符是 0，则只有当下标 i−1 处的字符是 0 时才符合单调递增；
如果下标 i 处的字符是 1，则下标 i−1 处的字符是 0 或 1 都符合单调递增，此时为了将翻转次数最小化，应分别考虑下标 i−1 处的字符是 0 和 1 的情况下需要的翻转次数，取两者的最小值。
实现方面有以下两点可以优化。
1. 可以将边界情况定义为 dp[−1][0] = dp[−1][1] = 0，则可以从下标 0 开始使用状态转移方程计算状态值。
2. 由于 dp[i−1] 有关，因此在计算状态值的过程中只需要维护前一个下标处的状态值，将空间复杂度降低到 O(1) 。
代码
Python3
class Solution: def minFlipsMonoIncr(self, s: str) -> int: dp0 = dp1 = 0 for c in s: dp0New, dp1New = dp0, min(dp0, dp1) if c == '1': dp0New += 1 else: dp1New += 1 dp0, dp1 = dp0New, dp1New return min(dp0, dp1)Java
class Solution { 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') { dp0New++; } else { dp1New++; } dp0 = dp0New; dp1 = dp1New; } return Math.min(dp0, dp1); } }C#
public class Solution { public int MinFlipsMonoIncr(string s) { int n = s.Length; int dp0 = 0, dp1 = 0; for (int i = 0; i < n; i++) { char c = s[i]; int dp0New = dp0, dp1New = Math.Min(dp0, dp1); if (c == '1') { dp0New++; } else { dp1New++; } dp0 = dp0New; dp1 = dp1New; } return Math.Min(dp0, dp1); } }