主題

LeetCode - 746. Min Cost Climbing Stairs 解題心得

Not In My Back Yard | 2021-01-06 00:00:11 | 巴幣 0 | 人氣 38

題目連結:


題目意譯:
階梯上,第 i 階有著非負成本 cost[i](索引值從 0 開始)。

一旦你付了成本價後,你可以選擇爬一階或是爬兩階。你需要找到最小的成本去抵達頂端,而且你可以從階梯 0 或是階梯 1 開始。

注:
cost 的長度介於 [2, 1000] 之間。
每個 cost[i] 是一個整數且介於 [0, 999] 之間。



範例測資:
範例 1:
輸入: cost = [10, 15, 20]
輸出: 15
解釋: 最便宜的方式為從 cost[1] 開始,付款之後直接走到頂端。

範例 2:
輸入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
輸出: 6
解釋: 最便宜的方式為從 cost[0] 開始,然後只走在成本為 1 的階梯上,但是要略過 cost[3]。


解題思維:
跟一般求一次走 1 階或走 2 階求走到頂端的方法數之題目很像,例如這題

定義 total[0] = cost[0] 、 total[1] = cost[1] 則 total[i] = cost[i] + min(total[i - 1], total[i - 2]) (對於 i > 1)。總之每個階梯就是找前兩階成本總額最小的加上該階本身的成本即是最小可能的成本。

而「頂端」可以視為成本為 0 的第 S + 1 階,其中 S 為 cost 陣列的長度。因此 total[S + 1] 即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作