【题解】剑指OfferII092.翻转字符（字符串）（动态规划）

题目链接

 力扣

题目描述

如果一个由 &＃39;0&＃39; 和 &＃39;1&＃39; 组成的字符串&＃xff0c;是以一些 &＃39;0&＃39;&＃xff08;可能没有 &＃39;0&＃39;&＃xff09;后面跟着一些 &＃39;1&＃39;&＃xff08;也可能没有 &＃39;1&＃39;&＃xff09;的形式组成的&＃xff0c;那么该字符串是 单调递增 的。

我们给出一个由字符 &＃39;0&＃39; 和 &＃39;1&＃39; 组成的字符串 s&＃xff0c;我们可以将任何 &＃39;0&＃39; 翻转为 &＃39;1&＃39; 或者将 &＃39;1&＃39; 翻转为 &＃39;0&＃39;。

返回使 s 单调递增 的最小翻转次数。

示例 1&＃xff1a;

输入&＃xff1a;s &＃61; "00110"
输出&＃xff1a;1
解释&＃xff1a;我们翻转最后一位得到 00111.
示例 2&＃xff1a;

输入&＃xff1a;s &＃61; "010110"
输出&＃xff1a;2
解释&＃xff1a;我们翻转得到 011111&＃xff0c;或者是 000111。
示例 3&＃xff1a;

输入&＃xff1a;s &＃61; "00011000"
输出&＃xff1a;2
解释&＃xff1a;我们翻转得到 00000000。
 

提示&＃xff1a;

1 <&＃61; s.length <&＃61; 20000
s 中只包含字符 &＃39;0&＃39; 和 &＃39;1&＃39;

解题思路

 首先看到这个题&＃xff0c;根据经验能判断出来是动态规划&＃xff0c;第一反应有点像编辑距离问题力扣&＃xff0c;但是看了看给定的数据范围&＃xff0c;不能让我们按照字符串长度建立二维的dp数组&＃xff0c;所以就考虑能不能二维数组一维是字符串的长度&＃xff0c;一维代表0和1&＃xff0c;参考了一下题解&＃xff0c;可以推出转移方程

其中f0(i)和f1(i)是代表修改后这一位是0还是1的

        当当前位为0的时候&＃xff0c;满足题意的只有前面的位数都为0的时候&＃xff0c;然后判断这一位本身是不是0&＃xff0c;不是的话需要增加一步从1变0的次数

        当当前为为1的时候&＃xff0c;满足题意可以前一位是0或者前一位是1&＃xff0c;只需要在两者之间选个最小的就可以了&＃xff0c;然后判断这一位本身是不是1&＃xff0c;不是的话需要增加一部从0变1的次数

题解

class Solution {
public:int dp[20005][2];int minFlipsMonoIncr(string s) {dp[0][1]&＃61;s[0]&＃61;&＃61;&＃39;1&＃39;?0:1;dp[0][0]&＃61;!dp[0][1];for(int i&＃61;1;i};