描述

如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是 单调递增 的。

我们给出一个由字符 '0' 和 '1' 组成的字符串 s，我们可以将任何 ‘0’ 翻转为 ‘1’ 或者将 ‘1’ 翻转为 ‘0’。

返回使 s 单调递增 的最小翻转次数。

示例

示例 1:

  1. 输入：s = "00110"
  2. 输出：1
  3. 解释：我们翻转最后一位得到 00111.

示例 2:

输入：s = "010110"
输出：2
解释：我们翻转得到 011111，或者是 000111。

示例 3:

输入：s = "00011000"
输出：2
解释：我们翻转得到 00000000。

提示

  • 1 <= s.length <= 20000
  • s 中只包含字符 '0' 和 '1'

解题思路

解法一：动态规划

写动态规划看状态转移方程，写状态转移方程看定义状态。
  • 定义dp[i][0], dp[i][0]表示前 i 个元素递增且第 i 个元素为 0 的最小翻转次数，
  • 定义dp[i][1]，dp[i][1]表示前 i 个元素递增且第 i 个元素为 1 的最小翻转次数。

由定义可知，如果前 i 个元素最后以 0 结尾且满足单调递增，那么前 i 个元素必须全部为 0，由此可得 dp[i][0] 的状态转移如下：
dp[i][0] = dp[i-1][0] + (s.charAt(i)=='0'?0:1);

由定义可知， dp[i][1]只要满足最后一个元素为 1 就行，那么前 i-1 个元素既可以为 0，也可以为1，因此 dp[i][1] 的状态转移如下：
dp[i][1] = min(dp[i-1][1], dp[i-1][0]) + (s.charAt(i)=='1'?0:1)；

最后取 dp[i][0], dp[i][1]中的较小的即可。

代码

class Solution {
    //dp[i][0]表示前i个元素，最后一个元素为0的最小翻转次数；
    //dp[i][1]表示前i个元素，最后一个元素为1的最小翻转次数
    public int minFlipsMonoIncr(String s) {
        int dp[][]=new int[s.length()][2];
        //初始化
        dp[0][0]=s.charAt(0)=='0'?0:1;
        dp[0][1]=s.charAt(0)=='1'?0:1;
        //状态转移
        for (int i = 1; i <s.length() ; i++) {
            dp[i][0]=dp[i-1][0]+(s.charAt(i)=='0'?0:1);
            dp[i][1]=Math.min(dp[i-1][0],dp[i-1][1])+(s.charAt(i)=='1'?0:1);
        }
        return Math.min(dp[s.length()-1][0],dp[s.length()-1][1]);
    }
}

空间优化：

class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        if (n == 1) return 0;
        int dp0 = s.charAt(0) == '0' ? 0 : 1;
        int dp1 = s.charAt(0) == '1' ? 0 : 1; 
        for (int i = 1; i < n; i++) {
            int tmp0 = dp0, tmp1 = dp1;
            dp0 = tmp0 + (s.charAt(i) == '0' ? 0 : 1);
            dp1 = Math.min(tmp0, tmp1) + (s.charAt(i) == '1' ? 0 : 1);
        }
        return Math.min(dp0, dp1);
    }
}

解法二：前缀和


将字符串翻转到单调递增