[数据结构与算法]动态规划---翻转字符（剑指offer-92）

原题链接

题目描述

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

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

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

示例1

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

示例2

输入：s = “010110”
输出：2
解释：我们翻转得到 011111，或者是 000111。

示例3

输入：s = “00011000”
输出：2
解释：我们翻转得到 00000000。

思路

对于每一个数字来说，我们有两种选择，翻转或者不翻转。
如果当前在求第i个数字，我们假设前i-1个数字都是符合条件的，即：0都在前，1都在后。那么第i-1个数字，也就是前面已经求完的符合条件的序列的最后一个数字，有2种情况，要么是0，要么是1。比如现在i是5，那么前面有可能0000（以0结尾），也有可能是0011（以1结尾）。那么既然要求最小的翻转次数，那就取他们的最小值呗！我们设f(i)表示计算到i时以0结尾的最小翻转次数，g(i)表示以1结尾。接下来详细讨论：

1. 以0结尾：
   此时，i-1必须是1，因为要满足所有的0都在前面，所以i前面不能是1结尾的！
   此时如果i为0，不需要翻转，f(i) = f(i - 1)
   此时如果i为1，需要翻转，f(i) = f(i - 1) + 1
2. 以1结尾：
   此时i-1是什么都无所谓，因为i是1，任何情况都满足要求，那就取最大值呗！
   此时如果i为0，需要翻转，g[i] = Math.min(g[i - 1], f[i - 1]) + 1
   此时如果i为1，不需要翻转，g[i] = Math.min(g[i - 1], f[i - 1])

代码

class Solution {
    public int minFlipsMonoIncr(String s) {
        int[] f = new int[s.length()]; //以0结尾
        int[] g = new int[s.length()]; //以1结尾
        if(s.charAt(0) == '0'){
            f[0] = 0;
            g[0] = 1;
        }else{
            f[0] = 1;
            g[0] = 0;
        }
        for(int i = 1; i < s.length(); i++){
            if(s.charAt(i) == '0'){
                f[i] = f[i - 1];
                g[i] = Math.min(g[i - 1], f[i - 1]) + 1;
            }else{
                f[i] = f[i - 1] + 1;
                g[i] = Math.min(g[i - 1], f[i - 1]);
            }
        }
        return Math.min(f[s.length() - 1], g[s.length() - 1]);
    }
}