926. flip string to monotonic increment

926. Flip the string to monotonic increment 【 Medium question 】【 A daily topic 】

Ideas ：

【 Dynamic programming 】

Refer to official solution code , And write the solution ideas in the notes .

Code ：

class Solution {
    
    public int minFlipsMonoIncr(String s) {
    
        int n = s.length();
        //dp0 and dp1 Respectively represent the current subscript i The corresponding characters are flipped to 0 and 1 Under the circumstances , Make substring [0,i] Incremental minimum number of flips , The initial values are all 0
        int dp0 = 0,dp1 = 0;
        for (int i = 0; i < n; i++) {
    
            //dp1 The meaning is , take i The position character is flipped to 1 when , Ensure substring [0,i] Incremental minimum number of flips , But will i The position is flipped to 1 There are two situations ：i-1 The position is  0  perhaps   by 1
            // therefore , To ensure the minimum number of turns , take dp1 Updated to dp0 and dp1 The lesser of 
            dp1 = Math.min(dp0,dp1);
            // Take out the current subscript i The character of position 
            char c = s.charAt(i);
            // If the current actual character is 1, Then flip it to 0 after ,dp0++, Flip it to 1 after ,dp1 unchanged 
            if (c == '1'){
    
                dp0++;
            }else {
    
                // If the current actual character is 0, Then flip it to 0,dp0 unchanged , Flip it to 1,dp1++
                dp1++;
            }
        }
        // At this time dp0 and dp1 It means   The string s The last character is flipped to 0 Or flip to 1, The minimum cumulative number of flips to keep the whole substring increasing , Just return the smaller value between the two 
        return Math.min(dp0,dp1);
    }
}

---