遇到一个动态规划问题，求解答。
小森马上就要迎来自己长达n天的寒假了，为不让自己无聊，他决定寒假每天都尽量出去运动。小森最喜欢的运动是滑雪和游泳。 但是并不是每天滑雪馆和游泳馆都开门，我们定义 a[i] 表示第 i 天的开门状态： 1.a[i]=0, 滑雪馆和游泳馆都不开门。 2.a[i]=1, 滑雪馆开门，但是游泳馆不开门。 3.a[i]=2, 滑雪馆不开门，但是游泳馆开门。 4.a[i]=3, 滑雪馆和游泳馆都开门。 但是小森又是一个讨厌重复的人，因此他不会连着两天做同样的运动，但是可以连续两天都不运动。也就是说，只有当滑雪馆开门并且前一天他没有去滑雪的时候他才能去滑雪。游 泳同理。因为运动是非常累的，所以小森每天最多只能做一种运动。现在小森已经得到了寒假时候滑雪馆和游泳馆的开门安排，即数组 a，他现在想知道自己不运动的天数的最小值。输入假期天数n1<=n<=100000，和包含n个数字的数组 a，表示场馆开门安排。输出一个数字，表示不运动的最小值天数。
写回答
-
本题充分利用四个开门状态，就可以使用动态规划： 小森只有 3 种可能的状态 ( 不运动、滑雪、游泳 )。本题要求不运动的最小值天数，可以反向思维，求运动的最大天数，然后用总天数减去最大运动天数即为最小运动天数dpi 表示第i天，选择休息（j=0）、游泳（j=1）、滑雪（j=2）时的最大运动天数状态转移方程为： dpi=max(dpi-1,dpi-1,dpi-1) 如果游泳馆开门 dpi=max(dpi-1+1, dpi-1+1) 否则 dpi=max(dpi-1,dpi-1,dpi-1) 如果滑雪馆开门 dpi=max(dpi-1+1, dpi-1+1) 否则 dpi=max(dpi-1,dpi-1, dpi-1) 遍历天数，完成上面状态转移，就完成了动态规划的过程。第一天的起始值也需要判断开门情况这里需要指出dpi 只是表示第i天滑雪时的最大运动，而不是第 i 天一定会滑雪 因此输入：5 [3,3,1,2,0] 输出：1
2021-12-23 18:37:03赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
