[leetcode/lintcode 题解] 腾讯面试题：最短休

描述

由于业绩优秀，公司给小Q放了 n 天的假，身为工作狂的小Q打算在假期中工作、锻炼或者休息。他有个奇怪的习惯：不会连续两天工作或锻炼。只有当公司营业时，小Q才能去工作，只有当健身房营业时，小Q才能去健身，小Q一天只能干一件事。给出假期中公司，健身房的营业情况，求小Q最少需要休息几天

1为营业 0为不营业

在线评测地址：lintcode领扣

样例1

输入:  company=[1,1,0,0],gym=[0,1,1,0]
输出: 2
样例解释: 小Q可以在第一天工作，第二天或第三天健身，小Q最少休息2天。

源代码

class Solution:
    """
    @param company: Company business
    @param gym: Gym business
    @return: Find the shortest rest day
    """
    def minimumRestDays(self, company, gym):
        # dp[i][j]: ith day, activity j. 0 = rest, 1 = work, 2 = gym
        dp = [[float('inf')] * 3 for _ in range(len(company))]
        dp[0][0] = 1
        if company[0]:
            dp[0][1] = 0
        if gym[0]:
            dp[0][2] = 0
        for i in range(1, len(company)):
            dp[i][0] = min(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]) + 1
            if company[i]:
                dp[i][1] = min(dp[i - 1][0], dp[i - 1][2])
            if gym[i]:
                dp[i][2] = min(dp[i - 1][0], dp[i - 1][1])

        return min(dp[len(company) - 1][0], dp[len(company) - 1][1], dp[len(company) - 1][2])

更多题解参考：leetcode/lintcode题解