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

题目描述

本题目来自LeetCode上的『926. 将字符串翻转到单调递增』

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

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

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

示例1：

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

提示

1 <= s.length <= 10^5
s[i] 为 '0' 或 '1'

题解

每个字符只有两种状态，设 $dp[i][0]$ 为第 $i$ 个位置的字符为 $0$ 所需要的最小变换次数，$dp[i][1]$ 同理。

当第 $i$ 个位置的字符为 $0$ 时，$i-1$ 位置的字符必须为 $0$，再加上自身变换的次数（若自身是 $1$，则需要一次变换）。
当第 $i$ 个位置的字符为 $1$ 时，$i-1$ 位置的字符可以为 $0$ 或 $1$，取两种情况的最小变换次数，再加上自身变换的次数（若自身是 $0$，则需要一次变换）。

有转移方程：
$$
dp[i][0]=dp[i-1][0]+(s[i]==’1’)
$$

$$
dp[i][1]=min(dp[i-1][0],dp[i-1][1])+(s[i]==’0’)
$$

初始情况下，$dp[0][0]=dp[0][1]=0$。
由于状态 $i$ 只和状态 $i-1$ 有关，因此可以优化空间，此时要特别注意计算顺序。
$$
dp1=min(dp0,dp1)+(s[i]==’0’)
$$

$$
dp0=dp0+(s[i]==’1’)
$$

代码

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int n = s.size();
        int dp0 = 0, dp1 = 0;
        for (int i = 0; i < n; ++i) {
            dp1 = min(dp0, dp1) + (s[i] == '0');
            dp0 = dp0 + (s[i] == '1');
        }
        return min(dp0, dp1);
    }
};