LeetCode 926题动态规划练习

926题题目介绍

创建一个二维数组dp[i][0]和dp[i][1]，分别储存一个S[i]这个数要变成0或1的时候需要翻转的次数。

初始化：

初始化

当我们开始循环时，S[i]分为两种情况：

1：S[i]='0'

不翻转它时，那么S[i]无需翻转，所以dp[i][0]=dp[i-1][0]。

把他变为1时，前面的数有两种情况，全部已经变为0或者1，即dp[i-1][0]和dp[i-1][1]，此时，这都符合我们递增的题目要求，我们只需要找出最少翻转的情况即可，即dp[i][1]=min(dp[i-1][0]+1,dp[i-1[1]+1)。

2：S[i]='1'

把它变为0时，因为要符合题目要求，所以变为0的时候前面的数必须是0，所以无需比较，直接dp[i][0]=dp[i-1][0]+1。

不翻转它时，此时有两种情况，全面的数都已经翻转成数字0此时开始翻转数字1，或者前面已经存在数字1，所以我们要比较两者那个最少翻转次数，所以dp[i][1]=min(dp[i-1][0],dp[i-1][1])。

核心代码