力扣每日一题2022-06-11中等题：将字符串翻转到单调递增

将字符串翻转到单调递增

• • 题目描述
  • 思路
  • • 动态规划
    • • Python实现
      • Java实现
      • C++实现

---

题目描述

将字符串翻转到单调递增

---

思路 动态规划

根据题意，单调递增字符串满足如下性质：

• 首个字符时0或1；
• 其余字符的每个字符，字符0前面的相邻字符一定是0，字符1前面的相邻字符可以是0或1。

当i>0时，如果字符串s的长度为i的前缀即s[0…i-1]单调递增，且s[i]与s[i-1]也满足上述单调递增的顺序，则长度为i+1的前缀s[0…i]也单调递增。所以可以用动态规划计算使字符串s单调递增的最小翻转次数。
因为s的每个位置可以是0或1，因此对每个位置需要分别计算该位置的字符是0和该位置的字符是1的情况下的最小翻转次数。
假设字符串的长度为n，对于0<=i 当i=0时，对应长度为1的前缀，一定满足单调递增，所以dp[0][0]和dp[0][1]的值取决于字符s[i]。如果s[0]为1，则dp[0][0]=1，如果s[0]为1，则dp[0][0]=1。
当1<=i 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)。
遍历s计算每个下标的状态值，遍历结束后，dp[i-1][0]和dp[i-1][1]的最小值即为字符串s单调递增的最小翻转次数。
实现过程中，可以将边界情况定义为dp[-1][0]=dp[-1][1]=0，就可以从下标0处开始使用状态转移方程计算状态值。并且因为dp[i]的值和dp[i-1]有关，所以只需要维护前一个下标处的状态值即可。

Python实现

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        dp0 = dp1 = 0
        for c in s:
            cur_dp0, cur_dp1 = dp0, min(dp0, dp1)
            if c == '1':
                cur_dp0 += 1
            else:
                cur_dp1 += 1
            dp0, dp1 = cur_dp0, cur_dp1
        return min(dp0, dp1)

Java实现

class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        int dp0 = 0, dp1 = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            int cur_dp0 = dp0, cur_dp1 = Math.min(dp0, dp1);
            if (c == '1') {
                cur_dp0++;
            } else {
                cur_dp1++;
            }
            dp0 = cur_dp0;
            dp1 = cur_dp1;
        }
        return Math.min(dp0, dp1);
    }
}

C++实现

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int dp0 = 0, dp1 = 0;
        for (char c : s) {
            int cur_dp0 = dp0, cur_dp1 = min(dp0, dp1);
            if (c == '1') {
                cur_dp0++;
            } else {
                cur_dp1++;
            }
            dp0 = cur_dp0;
            dp1 = cur_dp1;
        }
        return min(dp0, dp1);
    }
};