无锡网站建设设计/企业营销策划方案

题目：

如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是 单调递增 的。

我们给出一个由字符 '0' 和 '1' 组成的字符串 s，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。

返回使 s 单调递增 的最小翻转次数。

示例 :

输入：s = "00110"
输出：1
解释：我们翻转最后一位得到 00111.

思路：

我看到有前缀和的思路不错，但是这里还是放在动态规划里，所以还是用动态规划去解。

刚开始没想明白这里怎么用动态规划，看了一眼题解明白了。

递增有两种情况 

递增到n位，n位是0，则前面都是0

n位是1，前面可以1可以0

用一个二维数组记录当n位翻转次数，这么理解就和刷房子是差不多的

但是效率比较差

可以用常数去记录，可以提效率

复杂度：

时间：快排O（nlogn），查找O（n），就是O（nlogn）。

空间：没有额外空间，复杂度O（1）。

代码：

  //依旧使用动态规划int n = s.length();//只需要两种状态int[][] dp = new int[n][2];//初始化,第一个数，如果是以0结尾，是0就不翻反之翻。以1结尾同理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){//前面翻的次数加上这次翻不翻,第i是0，前面一定是0dp[i][0] = dp[i-1][0] + (s.charAt(i) == '0'?0:1);//前面可以是1也可以是0dp[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]);}

改用常数，但是可读性略差

public int minFlipsMonoIncr(String s) {//依旧使用动态规划//用两个变量记录两种状态 第n个是1的翻转次数，第n个是0的翻转次数int one = 0;int zero = 0;//开始遍历for(char ch : s.toCharArray()){//当前字符是0，要变这个为1前面可以1可以0，加一次就可以了if(ch =='0') one = Math.min(one,zero)+1;else{//当前是1，那one就不用了加了one = Math.min(one,zero);//改当前为0的话，zero++zero++;}}return Math.min(one,zero);}