題目

難度：★★☆☆☆
類型：數(shù)組，動態(tài)規(guī)劃

數(shù)組的每個索引做為一個階梯，第 i個階梯對應著一個非負數(shù)的體力花費值 costi。

每當你爬上一個階梯你都要花費對應的體力花費值，然后你可以選擇繼續(xù)爬一個階梯或者爬兩個階梯。

您需要找到達到樓層頂部的最低花費。在開始時，你可以選擇從索引為 0 或 1 的元素作為初始階梯。

注意
cost 的長度將會在 [2, 1000]。
每一個 cost[i] 將會是一個Integer類型，范圍為 [0, 999]。

示例 1
輸入: cost = [10, 15, 20]
輸出: 15
解釋: 最低花費是從cost[1]開始，然后走兩步即可到階梯頂，一共花費15。

示例 2
輸入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
輸出: 6
解釋: 最低花費方式是從cost[0]開始，逐個經(jīng)過那些1，跳過cost[3]，一共花費6。

解答

我們用動態(tài)規(guī)劃解決這個問題。

首先考慮特殊情況，當輸入階梯數(shù)組為空時，返回零，當輸入結題數(shù)組不超過2個元素時，返回其中的最小值；

我們定義數(shù)組dp，dp[i]表示到達下標為i的階梯需要消耗的最小能量。這里需要注意，頂部階梯實際上是被題目缺省掉的，即到達頂部階梯所需要消耗的能量為零，我們需要補回來。

條件
一次可以邁一步或者兩步。

初始化
i=0時，只有一個階梯，因此到達該階梯頂部需要的能量即為到達該階梯所需能量，為cost[0]；
i=1時，有兩個階梯，我們可以邁兩步，跳過第一級臺階，到達該階梯所需要的能量為到達第二級臺階所需能量，為cost[1]；

狀態(tài)轉移方程
i>1時，到達第i級臺階只有兩種選擇，一種是從第i-1級臺階邁一步，另一種是從i-2級臺階邁兩步，這兩種選擇消耗的最少能量分別是dp[i-1]+cost[i]和dp[i-2]+cost[i]，我們取兩者的最小值，即為到達下標為i的臺階所需的最少能量：
dp[i] = min(dp[i-1], dp[i-2]) + cost[i]

編碼實現(xiàn)：

class Solution:
    def minCostClimbingStairs(self, cost):
        if not cost:
            return 0
        if len(cost) <= 2:
            return min(cost)

        cost.append(0)
        dp = [None for _ in range(len(cost))]
        dp[0], dp[1] = cost[0], cost[1]
        for i in range(2, len(cost)):
            dp[i] = min(dp[i-2], dp[i-1]) + cost[i]
        print(dp)
        return dp[-1]

如有疑問或建議，歡迎評論區(qū)留言~