一魚多吃 用費式數列的模型來解 Min Cost Climbing Stairs_Leetcode #746_精選75題

這題算是前面那題Climbing stairs的變形題，有點小變化，但是稍微想一下還是能推導出來，算是很好的一維動態規劃1D DP練習題。

回憶一下題過的DP解題框架與三大步驟

1. 定義狀態 [我在哪裡]

2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]

3. 釐清初始狀態(也可以說是遞迴的終止條件) [第一步怎麼走，怎麼出發的]

題目敘述

詳細的原文題目可以在這裡看到 Min Cost Climbing Stairs

題目說每次可以爬一階樓梯或兩階樓梯，爬到第i層階梯時，會有一個附帶成本cost[i]

題目問爬到終點(最高階樓梯)的最小成本是多少。

測試範例:

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.

這裡我們走過一遍DP解題框架

1. 定義DP狀態 
[我在哪裡]

這題滿直覺的，就令DP[n]為爬n階樓梯的最小成本。

最後所求就是min( DP[n-1], DP[n-2] )，因為最後一次要嘛踩一階可以到最後一層，要嘛踩兩階可以到最後一層。

2. 定義DP狀態轉移關係式(通則)
[我從哪裡來] => [答案從哪裡推導而來]

題目說每次可以爬一階樓梯或兩階樓梯，也就是說

假如當下這層是第i階樓梯，那麼我們有兩種方式可以到達這裡:

一種是先到i-1階，接著再爬一階樓梯，那麼我們就到了第n階。

另一種是先到i-2階，接著再爬兩階樓梯，那麼我們就到了第n階。

題目要求我們計算最小成本，所以是取min最小值。

然後，別忘了，抵達第i層階梯時，本身有一個附帶成本cost[i]