golang 刷leetcode：将字符串翻转到单调递增

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

给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0 。

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

示例 1：

输入：s = "00110"

输出：1

解释：翻转最后一位得到 00111.

示例 2：

输入：s = "010110"

输出：2

解释：翻转得到 011111，或者是 000111。

示例 3：

输入：s = "00011000"

输出：2

解释：翻转得到 00000000。

提示：

1 <= s.length <= 105

s[i] 为 '0' 或 '1'

解题思路：

1，本题很容拆分子问题

假设dp0[i],表示i位置是0，也就是0～i位置都是0 需要的最小翻转次数；假设dp1[i],表示i位置是1，也就是0～k位置为0，k~i 位置为i需要的最小翻转次数

2，那么对于i+1位置，如果s[i+1]=='0',

dp0[i+1]=dp0[i],都是0，不需要翻转

dp1[i+1]=dp1'[i]+1,需要翻转一次，变成1

3，对于i+1位置，如果s[i]=='1'

dp0[i+1]=dp0[i]+1,需要翻转一次，变成0

dp1[i+1]=dp1[i]'，都是1，不需要翻转

4，对于i+1位置，每次计算dp0就是统计1的个数；

5，对于i+1位置，计算dp1，需要看下k到i位置，变成0还是1，谁的代价更小

即上面的dp1'[i]=min(dp1[i],dp0[i]

6,由于每个位置只依赖前一个位置，可以将一维动态规划压缩到常数

代码实现

func minFlipsMonoIncr(s string) int {
   dp0,dp1:=0,0
   for _,v:=range s{
       dp1=min(dp0,dp1)
       if v=='1'{
          dp0++
       }else{
          dp1++
       }
   }
   return min(dp0,dp1)
}

func min(a,b int)int{
    if a<b{
        return a
    }
    return b
}

复制