LintCode-数字翻转-动态规划

描述

给你一个01构成的数组。请你找出最小翻转步数，使得数组满足以下规则：
1的后面可以是1或者0，但是0的后面必须是0。

输入的数组长度n <= 100000。

样例

给出 array = [1,0,0,1,1,1] , 返回2。

解释：

把两个0翻转成1。
给出 array = [1,0,1,0,1,0] , 返回2。

解释：

把第二个1和第三个1都翻转成0。

代码

class Solution:
    """
    @param nums: the array
    @return: the minimum times to flip digit
    """
    def flipDigit(self, nums):
        # Write your code here
        n = len(nums)
        dp = [[0, 0] for i in range(n+1)]
        for i in range(1, n+1):
            if nums[i-1] == 0:
                dp[i][0] = min(dp[i-1][1], dp[i-1][0])
                dp[i][1] = dp[i-1][1] + 1
            elif nums[i-1] == 1:
                dp[i][0] = min(dp[i-1][1], dp[i-1][0]) + 1
                dp[i][1] = dp[i-1][1]
        return min(dp[n][0], dp[n][1])

思路

序列型动态规划，首先，每个状态i有两种存在的可能性：0和1，所以要分开记录可能转变成0或1需要的在此时需要的最小步数。且1的后面可以是1或者0，但是0的后面必须是0，就意味着0的前面可以是1或者0，但是1的前面必须是1。则当nums中的num为0时，它可以选不变化，然后从上个状态的0和1的dp中取个最小值，也可以选择变化为1，但是只能选择上个状态的1的dp的值加1；当num为1时，相似的，它可以选不变化，然后只能从上个状态的1的dp的值加1，也可以选择变化为0，然后选择上个状态的0和1的dp中取个最小值。

题目来源

https://www.lintcode.com/problem/digital-flip/description