算法笔试模拟题精解之“寒假活动”

在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：

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 只是表示第i天滑雪时的最大运动，而不是第i天一定会滑雪

时间复杂度：O(n)

空间复杂度：O(kn)

是不是有思路了呢，点击链接立刻答题：>>

寒假活动 另有在线编程3月份比赛正式开启！机械键盘等你拿！