算法筆試模拟題精解之“codancer上樓”

線上程式設計介紹

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

https://developer.aliyun.com/coding

本文為大家介紹其中的 第113題：codancer上樓 的題目解析，具體如下：

題目描述

題目等級：中等

知識點：DP

檢視題目：codancer上樓

codancer來到了一棟大樓前，現在他要上樓。

如果codancer從第x層走樓梯到第y層(y>x)，那麼他所花費的時間是a[x]+a[x+1]+…+a[y]；

如果他從x層坐電梯到第y層，那麼他所花費的時間是c+(b[x]+b[x+1]+…+b[y])，因為他等電梯的時間為c。

現在codancer想知道 從第1層到第n層需要最少需要多長時間？

有四個入參，第一個輸入一個正整數n，表示要上到第n層樓；

第二個輸入一個整數c(1<=n<=100000,1<=c<=1000)，表示等電梯花費的時間；

接下來輸入兩個數組a和b，數組中n-1個數字代表數組a和b(1<=a[i],b[i]<=1000)，分别表示爬樓梯和乘電梯每層樓花費的時間。

輸出codancer到達第n層最少需要的時間。

示例1

輸入：

4

1

[3,2,3]

[1,2,3]

輸出：

7

注意

直接坐電梯從1樓到4樓即可，答案是1+1+2+3=7

解題思路：動态規劃

對于每層需要儲存兩個值。一個是這層選擇選擇走樓梯的最小花費，記為Ta(i)。另一個是這層選擇坐電梯的最小花費，記為Tb(i)。

狀态轉移（字母與題幹中所給含義相同）

Ta(i+1) = min(Ta(i)+a(i+1)，Tb(i)+a(i+1))
Tb(i+1) = min(Ta(i)+b(i+1)+c，Tb(i)+b(i+1))           

這樣一直計算到最後一層即可。

時間複雜度O(n)

空間複雜度O(2*n)

看完之後是不是有了想法了呢，快來練練手吧>>