LeetCode 926. 将字符串翻转到单调递增 递归实现动态规划 两种解法

这个题做了一个多小时，考虑复杂了。

• 开始推动规没有推出来，然后找到一个递推关系：从左往右，如果是0，则不需要变动；如果是1，则有两种选择（1）将1变为0（2）将1后面的所有数字变为1，这两种方法中的变动数字最小的方法就是最佳方法，然后依次递推，很容易写出递归程序。但是这里面存在问题，如果直接计数1后面0的个数会超时；开数组提前保存会爆内存。所以在其中采用动规，在调用返回时记录0的数量。（这里的动规用for循环写也可以）
• 另一种方法是看两个数字间的缝隙的左右两侧的需要变动的0和1的数量，加和最小为最优。

java代码如下：

• 递归实现动态规划

class Solution {
    public int count_0;

    public Solution(){
        
        count_0 = 0;
    }

    public int minFlipsMonoIncr(String S) {

        if(S.length() <= 0) return 0;
        int min = 999;
        if(S.charAt(0) == '0'){
            min = minFlipsMonoIncr(S.substring(1));
            count_0++;
        }
        else{
            min = minFlipsMonoIncr(S.substring(1)) + 1;
            if(min > count_0) min = count_0;
        }
        return min;
    } 
}

• 另一种解法

class Solution {
    public int minFlipsMonoIncr(String S) {

        int[] count_0 = new int[S.length() + 5];
        int[] count_1 = new int[S.length() + 5];
        count_0[S.length()] = 0;
        count_1[0] = 0;
        for (int i = S.length() - 1, sum = 0; i >= 0; i--) {
            if (S.charAt(i) == '0') {
                count_0[i] = ++sum;
            } else {
                count_0[i] = sum;
            }
        }
        for (int i = 1, sum = 0; i <= S.length(); i++) {
            if (S.charAt(i - 1) == '1') {
                count_1[i] = ++sum;
            } else {
                count_1[i] = sum;
            }
        }
        int min = 99999;
        for (int i = 0; i <= S.length(); i++) {
            if (count_0[i] + count_1[i] < min) {
                min = count_0[i] + count_1[i];
            }
        }
        return min;
    }
}