Li Kou today's question 926 Flip string to monotonic increment

926. Flip the string to monotonic increment

Ideas :

Dynamic programming , State transition equation ： When there is a 0 When , It can be done to 0 Conduct +1 Operate or make all of the preceding 1 become 0, State transition equation ret=min(ret + 1, num_1);

class Solution {
    public int minFlipsMonoIncr(String s) {
        char[] cs = s.toCharArray();
        // First convert the string of words into an array ,ret Is used to record the minimum operand ,num_1 It's for recording 1 The number of 
        int n = cs.length, ret = 0 , num_1 = 0, num_0 = 0;
        // for(int i = 0;i <n; i++){
        //     if(cs[i] == '0'){
        //         // encounter 0 There are two operations , One is to 0 Additive transformation 1, Operands +1. Or put this 0 Ahead 1 become 0, The operand depends on 1 The number of , That is to say num_1.
               
        //         ret =  Math.min(ret+1,num_1);
        //     } else{
        //         // As long as you don't meet 0  That's it 1, therefore num_1 want ++ ,
        //         num_1++;
        //     }
        // }

        // The same way of thinking , This time it is traversal from back to front , encounter 1 There are two operations , One is to 1 become 0 Operands +1, The other is to put this 1 After that 0 All become one 

        for(int i = n; i > 0 ; i--){
            if(cs[i-1] == '1'){
                ret = Math.min(ret + 1, num_0);
            }else{
                num_0++;
            }
        }
        return ret; 
    }
}

2022/6/11