# 926. Flip String to Monotone Increasing
###### tags: `LeetCode`
## **Link**
https://leetcode.com/problems/flip-string-to-monotone-increasing/

## **雙向版本（因為單向版本的ans設錯）**

class Solution {
public:
    int minFlipsMonoIncr(string s) 
    {
        vector<pair<int,int>> vec;
        vector<int> cnt(2);
        int ct=0,ans=2147483647;
        char now=s[0];
        for(char v:s) // 壓縮陣列 其實好像沒必要就是了w
        {
            if(now==v)
                ++ct;
            else
            {
                vec.push_back(make_pair(now-'0',ct));
                ct=1;
                now=v;
            }
        }
        vec.push_back(make_pair(now-'0',ct));
        for(int i=0;i<vec.size();++i) // 算0數量
            if(vec[i].first==0)
                cnt[0]+=vec[i].second;
        for(int i=0;i<vec.size();++i) // 左邊往右邊
        {
            if(vec[i].first==0)
                cnt[0]-=vec[i].second;
            else
                cnt[1]+=vec[i].second;
            ans=min(ans,cnt[0]+cnt[1]);
        }
        cnt[0]=0;
        cnt[1]=0;
        for(int i=0;i<vec.size();++i) // 算1數量
            if(vec[i].first==1)
                cnt[1]+=vec[i].second;
        for(int i=vec.size()-1;i>=0;--i) // 右邊往左邊
        {
            if(vec[i].first==0)
                cnt[0]+=vec[i].second;
            else
                cnt[1]-=vec[i].second;
            ans=min(ans,cnt[0]+cnt[1]);
        }
        return ans;
    }
};

## **單向版本（就是ans有設對的話只要走一次w）**

class Solution {
public:
    int minFlipsMonoIncr(string s) 
    {
        vector<pair<int,int>> vec;
        vector<int> cnt(2);
        int ct=0;
        char now=s[0];
        for(char v:s) // 壓縮陣列 其實好像沒必要就是了w
        {
            if(now==v)
                ++ct;
            else
            {
                vec.push_back(make_pair(now-'0',ct));
                ct=1;
                now=v;
            }
        }
        vec.push_back(make_pair(now-'0',ct));
        for(int i=0;i<vec.size();++i) // 算0數量
            if(vec[i].first==0)
                cnt[0]+=vec[i].second;
        int ans=cnt[0]; // ans預設為0的總數
        for(int i=0;i<vec.size();++i) // 左邊向右邊
        {
            if(vec[i].first==0)
                cnt[0]-=vec[i].second;
            else
                cnt[1]+=vec[i].second;
            ans=min(ans,cnt[0]+cnt[1]);
        }
        return ans;
    }
};

## **大佬的超短dp解**
<font color="#00ffff">想法是，ct[0]存的是<font color="#00ff00">加入這個數字之前的<font color="#ff0000">最佳解</font>所需要翻轉的次數</font>，所以如果接下來要加進來的數字是0，ct[0]就必須增加1（因為是在最佳解後面，所以改成1才<font color="#ff0000">必定是可行解</font>）。</font>

<font color="#00ffff">然後，有可能會改變最佳解的情況就只有<font color="#ff0000">**左邊的1總數比最佳解少**</font>這種情況（全部改成0），所以用ct[1]來計算到目前為止的1總數，並在每次迴圈結束之後用min來判斷誰是最佳解。</font>

class Solution {
public:
    int minFlipsMonoIncr(string s) 
    {
        int ct[2]={};
        for(char v:s)
        {
            ++ct[v-'0'];
            ct[0]=min(ct[0],ct[1]);
        }
        return ct[0];
    }
};

## date
<font color="#00ffff">**202.01.17**</font>

{%hackmd @nnks8908/background_leetcode %}