📃 题目描述

题目链接：

• 剑指 Offer II 092. 翻转字符 - 力扣（LeetCode） (opens new window)
• 926. 将字符串翻转到单调递增 - 力扣（LeetCode） (opens new window)

🔔 解题思路

二维数组 dp[i][2]：

• dp[i][0]: 把字符串 S[0, i] 变成符合要求的字符串, 并且最后一个字符是'0'所需要的最少翻转次数
• dp[i][1]: 把字符串 S[0, i] 变成符合要求的字符串, 并且最后一个字符是'1'所需要的最少翻转次数

状态转移方程：

• dp[i][0] = dp[i - 1][0] + (s.charAt(i) == '0' ? 0 : 1); 把字符串 S[0, i] 变成符合要求的字符串, 并且最后一个字符是'0'，那么符合要求的字符串 S[0, i - 1] 的最后一位也一定得是 0。其次，如果 s.charAt(i) 是 0 的话，那么就不要翻转，如果 s.charAt(i) 是 1 的话，就需要翻转成 0
• dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + (s.charAt(i) == '1' ? 0 : 1); 把字符串 S[0, i] 变成符合要求的字符串, 并且最后一个字符是'1'，那么符合要求的字符串 S[0, i - 1] 的最后一位可以是 0 也可以是 1。其次，如果 s.charAt(i) 是 0 的话，那么就需要翻转成 1，如果 s.charAt(i) 是 1 的话，就不需要翻转

class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        // dp[i][0]: 把字符串 S[0, i] 变成符合要求的字符串, 并且最后一个字符是'0'所需要的最少翻转次数
        // dp[i][1]: 把字符串 S[0, i] 变成符合要求的字符串, 并且最后一个字符是'1'所需要的最少翻转次数
        int[][] dp = new int[n][2];

        dp[0][0] = (s.charAt(0) == '0') ? 0 : 1;
        dp[0][1] = (s.charAt(0) == '1') ? 0 : 1;

        for (int i = 1; i < n; 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[n - 1][0], dp[n - 1][1]);
    }
}

空间压缩：

class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        // dp[0]: 把字符串 S[0, i] 变成符合要求的字符串, 并且最后一个字符是'0'所需要的最少翻转次数
        // dp[1]: 把字符串 S[0, i] 变成符合要求的字符串, 并且最后一个字符是'1'所需要的最少翻转次数
        int[] dp = new int[2];

        dp[0] = (s.charAt(0) == '0') ? 0 : 1;
        dp[1] = (s.charAt(0) == '1') ? 0 : 1;

        for (int i = 1; i < n; i ++) {
            int temp0 = dp[0];

            dp[0] = dp[0] + (s.charAt(i) == '0' ? 0 : 1);
            dp[1] = Math.min(temp0, dp[1]) + (s.charAt(i) == '1' ? 0 : 1);
        }

        return Math.min(dp[0], dp[1]);
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：