算法筆試模拟題精解之“寒假活動”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

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月份比賽正式開啟！機械鍵盤等你拿！