在线编程介绍
阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding
题目描述
等级：中等
知识点：DP
查看题目：寒假活动
小森马上就要迎来自己长达 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，表示场馆开门安排。
输出一个数字，表示不运动的最小值天数。
示例1
输入：
5
[3,3,1,2,0]
输出：
1
注意：
小森的最优策略是第一天滑雪，第二天游泳，第三天滑雪，第四天游泳，第五天不运动。
题解思路：动态规划
本题充分利用四个开门状态，就可以使用动态规划：
小森只有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天一定会滑雪
时间复杂度：O(n)
空间复杂度：O(kn)
是不是有思路了呢，点击链接立刻答题：>>寒假活动
