leetcode 926. Flip String to Monotone Increasing 将字符串翻转到单调递增

Problem: 926. Flip String to Monotone Increasing 将字符串翻转到单调递增

动态规划的，dp[n][2]，n代表字符串长度，2代表以0或者1结束，dp[0][1]是翻转以后的字符串ss，ss[0]‘1’，dp[0][0]代表ss[0]‘0’，dp[i][0]代表翻转以后的字符串ss中ss[i]'0’的最小翻转次数, dp[i][1]代表翻转以后的字符串ss中ss[i]'1’的最小翻转次数

递推公式是：若s[i]==‘0’，则dp[i][0] = dp[i-1][0];此时不需要翻转，则dp[i][1] = min( dp[i-1][0], dp[i-1][1]) + 1;此时需要翻转

若s[i]==‘1’，则dp[i][0] = dp[i-1][0] + 1;此时需要翻转，则dp[i][1] = min(dp[i-1][1], dp[i-1][0]);此时不需要翻转

最后返回 min(dp[n-1][0], dp[n-1][1])

Code

class Solution { public: int minFlipsMonoIncr(string s) { int n = s.size(); int l = 0, r = n - 1; vector<vector<int>> dp(n, vector<int>(2, 0)); if(s[0]=='0') { dp[0][1] = 1; } else { dp[0][0] = 1; } for(int i = 1; i < n; i++) { if(s[i]=='0') { dp[i][0] = dp[i-1][0]; dp[i][1] = min( dp[i-1][0], dp[i-1][1]) + 1; } else { dp[i][0] = dp[i-1][0] + 1; dp[i][1] = min(dp[i-1][1], dp[i-1][0]); } } return min(dp[n-1][0], dp[n-1][1]); } };