926. 将字符串翻转到单调递增

926. 将字符串翻转到单调递增【中等题】【每日一题】

思路：

【动态规划】

参考官解代码，并将解题思路写在注释里。

代码：

class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        //dp0和dp1分别表示当前下标i对应的字符翻转为0和1的情况下，使子串[0,i]递增的最小翻转次数，初值均为0
        int dp0 = 0,dp1 = 0;
        for (int i = 0; i < n; i++) {
            //dp1的含义是，将i位置字符翻转为1时，保证子串[0,i]递增的最小翻转次数，但将i位置翻转为1有两种情况：i-1位置为 0 或者 为1
            //因此，为了保证翻转次数最小，将dp1更新为dp0和dp1的较小值
            dp1 = Math.min(dp0,dp1);
            //取出当前下标i位置的字符
            char c = s.charAt(i);
            //如果当前实际字符是1，那么将其翻转为0后，dp0++，将其翻转为1后，dp1不变
            if (c == '1'){
                dp0++;
            }else {
                //如果当前实际字符是0，那么将其翻转为0，dp0不变，将其翻转为1，dp1++
                dp1++;
            }
        }
        //此时的dp0和dp1表示的是 将字符串s最后一个字符翻转为0或者翻转为1，使得整个子串保持递增的最小累计翻转次数，返回两者之间的较小值即可
        return Math.min(dp0,dp1);
    }
}