【秃头】奋斗逼最少可以休息几天

996的未来是什么？

是升职加薪吗？

是年入百万吗？

是财务自由、40岁光荣退休衣食无忧吗？

错！以上全错！996的未来，是007

除了非暴力不合作之外，还有很多抗争方式

好了，回归到正题。前几天碰到了一道关于奋斗逼的题，题目是这样的：

由于表现突出，公司给奋斗逼小Q放了N天假。但作为一个奋斗逼，小Q不打算全部休息，而是上班、健身或休息，但会按照以下规则：不连续两天工作，也不连续两天健身（嗯，可能是怕猝死吧）。并且，只有在公司开门时才能去上班、健身房营业时才能去健身，每天也只能在上班/健身/休息中做一件事。已知公司和健身房的营业时间（1代表营业，0代表休业），求奋斗逼小Q最少能在这期间休息几天。

例：company=[1,1,0,0], gym=[0,1,1,0]  

答案：2

解释：班、健、休、休 或 班、休、健、休

果然是个奋斗逼，放假了还考虑去上班。不过显然，他的觉悟还不够高，上班为什么不能连续两天？为了民族复兴、为了赶英超美，奋斗逼应该连续工作200天。如果做不到，那就是思想路线有问题，一定通美通英通日，受到了资产阶级自由化思想的腐蚀！

从做题的角度来看，这道题是简单的，很显然是动态规划，应该以当天做什么来分类设三个数组work、exercise、rest，记录如果当天是上班/健身/休息的话最少可以休息几天。显然可知，它们之间的状态转移关系是这样的：

rest[n]=min(rest[n-1],work[n-1],exercise[n-1])+1

公司开门：work[n] = min(rest[n-1],exercise[n-1]) 

健身房开门：exercise[n] = min(rest[n-1],work[n-1])

最终答案：rest[N],work[N],exercise[N]中的最小值

如果公司或健身房不开门，对应的work[n],exercise[n]其实是不存在的，可以设为N。

这时候空间复杂度是O（N），但其实一看，第n天只和第n-1天相关，所以只要保存前一天的值就可以了，压缩到O（1），所以就变成了这样：

class Solution:
    """
    @param company: Company business
    @param gym: Gym business
    @return: Find the shortest rest day
    """
    def minimumRestDays(self, company, gym):
        
        l=len(company)
        
        work,exercise,rest=0,0,0
        for i in range(l):
            work_tmp,exercise_tmp=l,l
            if gym[i]==1:
                exercise_tmp=min(work,rest)
            if company[i]==1 :
                work_tmp=min(exercise,rest)
                
            rest=min(work,rest,exercise)+1    
            work=work_tmp
            exercise=exercise_tmp
                
        return min(work,exercise,rest)

这样就搞定了。那么为什么标题说秃头呢？

因为只要你像本宝宝一样多在业余时间学习、做题，你的头发就会和我一样少……

相关阅读：