[LeetCode] 926. Flip String to Monotone Increasing My SubmissionsBack to Contest

题：https://leetcode.com/contest/weekly-contest-107/problems/flip-string-to-monotone-increasing/

题目

A string of '0’s and '1’s is monotone increasing if it consists of some number of '0’s (possibly 0), followed by some number of '1’s (also possibly 0.)

We are given a string S of '0’s and '1’s, and we may flip any ‘0’ to a ‘1’ or a ‘1’ to a ‘0’.

Return the minimum number of flips to make S monotone increasing.

Example 1:

Input: "00110"
Output: 1
Explanation: We flip the last digit to get 00111.

Example 2:

Input: "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.

Example 3:

Input: "00011000"
Output: 2
Explanation: We flip to get 00000000.

Note:

1. 1 <= S.length <= 20000
2. S only consists of ‘0’ and ‘1’ characters.

题目大意

给定字符串 由 0,1组成，求 换最少的 字符使得 字符串 不递减。

思路

方法一 动态规划

状态：
dp[i][0] str[0:i] 最后字符为 0 时，最少 换字符数。
dp[i][1] str[0:i] 最后字符为 1 时，最少 换字符数。

状态转移方程：

            if(S.charAt(i-1) == '0'){
                dp[i][0] = dp[i-1][0];
                dp[i][1] = dp[i-1][1]+1;
            }
            else{
                dp[i][0] = dp[i-1][0]+1;
                dp[i][1] = Math.min(dp[i-1][1],dp[i-1][0]);
            }

code

class Solution {
    public int minFlipsMonoIncr(String S) {
        int strlen = S.length();
        int[][] dp = new int[strlen+1][2];
        dp[0][0] = dp[0][1] = 0;
        for(int i = 1;i<=strlen;i++){
            if(S.charAt(i-1) == '0'){
                dp[i][0] = dp[i-1][0];
                dp[i][1] = dp[i-1][1]+1;
            }
            else{
                dp[i][0] = dp[i-1][0]+1;
                dp[i][1] = Math.min(dp[i-1][1],dp[i-1][0]);
            }
        }
        return Math.min(dp[strlen][0],dp[strlen][1]);
    }
}

由于dp[i]只用到 前一个 dp[i-1]，可以 简化dp，使用一维dp。

class Solution {
    public int minFlipsMonoIncr(String S) { 
        int[] dp = new int[2];
        for(int i = 0;i<S.length();i++){
            if(S.charAt(i)=='0')
                dp[1] = dp[1]+1; 
            else{
                dp[1] = Math.min(dp[1],dp[0]);
                dp[0] = dp[0] + 1;
            }
        }
        return Math.min(dp[0],dp[1]);
    }
}