【腾讯2020秋招】 假期


遇到这种题,第一想到动态规划,利用dp【n+1】【3】,工作--0,健身---1,休息---2,分别代表一个状态,可以画一个三个状态的转换图

其次我们需要明白dp【i】【0】的状态,代表在第i天,如果小Q去工作,那么前i天中休息的最少天数,这个定义是取决于题目的定义,一个意思。

看题目意思,只有公司开门才能工作,那么需要判断公司开不开门,如果开,

dp【i】【0】的状态是取决于前i-1天的状态,因为第i天已经决定是工作,那么就去dp【i-1】【1】和dp【i-1】【2】,因为第i-1天可能是健身或休息。

这是一类题,需要对初始值好好规划一下,如果有n天,数组长度可以设为n+1

dp[0]可以0或1,正无穷大或负无穷大,这个,我们可以去试一试

代码如下:


©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容