[数据结构与算法]leetcode 1888 反转构造交替字符串

解法：动态规划
考虑类型1：会把字符串分成n种状态，计算出初始状态后，我们可以通过状态转移方程来获得其余状态的值。只需考虑上一位的值即可，代码如下：

class Solution {
public:
    int minFlips(string s) {
        int n = s.size();

        int dp[n][2];
        memset(dp, 0, sizeof(dp));

        for(int i=0;i<n;i++)
        {
            if(i&1)
            {
                if(s[i] == '0')dp[0][0]++;
                else dp[0][1]++;
            }
            else
            {
                if(s[i] == '0')dp[0][1]++;
                else dp[0][0]++;
            }
        }

        int ans = min(dp[0][0], dp[0][1]);
        for(int i=1;i<n;i++)
        {
            dp[i][0] = dp[i-1][1];
            dp[i][1] = dp[i-1][0];
            if(s[i-1] == '0')dp[i][0]--;
            else dp[i][1]--;

            if(n&1)
            {
                if(s[i-1] == '0')dp[i][1]++;
                else dp[i][0]++;
            }
            else
            {
                if(s[i-1] == '1')dp[i][1]++;
                else dp[i][0]++;
            }
            int tmp = min(dp[i][0], dp[i][1]);
            if(tmp < ans)ans = tmp;
        }
        return ans;
    }
};

上面的代码可以进行两个优化：：
优化1：可以每次只存上一个的数，无需记录dp数组
优化2：dp的两维相加等于len，只存一个数即可。

class Solution {
public:
    int minFlips(string s) {
        int n = s.size();

        int zero = 0;        
        for(int i=0;i<n;i++)
        {
            if(i&1 && s[i] == '0')zero++;
            else if(!(i&1) && s[i] == '1')zero++;
        }

        int ans = min(zero, n-zero);
        for(int i=1;i<n;i++)
        {
            zero = n - zero;
            if(s[i-1] == '0')zero--;

            if(n&1)
            {
                if(s[i-1] == '1')zero++;
            }
            else
            {
                if(s[i-1] == '0')zero++;
            }
            ans = min({zero, n-zero, ans});
        }
        return ans;
    }
};