926. Flip String to Monotone Increasing 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();

        // 定义 dp[i][j] 为 s[i] 值为 j 时 s[0, i] 所需的最小翻转次数
        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 < dp.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[n - 1][0], dp[n - 1][1]);
    }
}

注意三目运算符需要加括号，因为三目运算符优先级低于加减号。

References

926. Flip String to Monotone Increasing
剑指 Offer II 092. 翻转字符
The Java™ Tutorials > Learning the Java Language > Language Basics > Operators)