我们先来看题目描述如果一个二进制字符串是以一些 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*5s [i] 为 0 或 1解决方案动态规划单调递增的字符串满足以下性质首个字符是 0 或 1其余的每个字符字符 0 前面的相邻字符一定是 0字符 1 前面的相邻字符可以是 0 或 1。当 i0 时如果字符串 s 的长度为 i 的前缀即 s[0..i−1] 单调递增且 s[i] 和 s[i−1] 也满足上述单调递增的顺序则长度为 i1 的前缀 s[0..i] 也单调递增。因此可以使用动态规划计算使字符串 s 单调递增的最小翻转次数。由于字符串 s 的每个位置的字符可以是 0 或 1因此对于每个位置需要分别计算该位置的字符是 0 和该位置的字符是 1 的情况下的最小翻转次数。假设字符串 s 的长度是 n对于 0≤in用 dp[i][0] 和 dp[i][1] 分别表示下标 i 处的字符为 0 和 1 的情况下使得 s[0..i] 单调递增的最小翻转次数。当 i0 时对应长度为 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≤in 时考虑下标 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) 。代码Python3class 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)Javaclass 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); } }