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])。


核心代码
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容