1、思路

• 用一个二维数组（2行N列）来做dp，数组的第一行表示将当前字符变成0所需要的最少翻转次数，第二行表示将当前字符变成1所需的最少翻转次数；

• dp[0][i]表示将s[i]这个字符变成0，且整个字符串保持单调递增所需的最少翻转次数，这个状态只与dp[0][i - 1]有关，若dp[0][i] == '0'，则当前状态等于上一状态，不需要改变，若dp[0][i] == '1'，则需要把当前的字符1变成0，即在上一状态的基础上再加一个操作；

• dp[1][i]表示将s[i]这个字符变成1，且整个字符串保持单调递增所需的最少翻转次数，这个状态与dp[0][i - 1]和dp[1][i - 1]有关，若dp[0][i] == '1'，则当前状态等于上两个状态的最小值（因为上两个状态已经达到单调递增的条件了），不需要改变，若dp[0][i] == '0'，则需要把当前的字符0变成1，即在上两个状态最小值的基础上再加一个操作；

• 又因为当前状态只与前一个状态有关，所以可以用一个2 X 2的数组来进行动态规划；

2、代码

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        if (s.empty()) return 0;
        int len = s.length();

        vector<vector<int>> dp(2, vector<int>(2, 0));
        dp[0][0] = s[0] == '0' ? 0 : 1;         //初始化
        dp[1][0] = s[0] == '1' ? 0 : 1;

        for (int i = 1; i < len; ++ i)
        {
            int prev0 = dp[0][(i - 1) % 2];     //保存前两个状态
            int prev1 = dp[1][(i - 1) % 2];

            dp[0][i % 2] = prev0 + (s[i] == '0' ? 0 : 1);
            dp[1][i % 2] = min(prev0, prev1) + (s[i] == '1' ? 0 : 1);
        }

        return min(dp[0][(len - 1) % 2], dp[1][(len - 1) % 2]);     //结果为两种状态的最小值
    }
};