數(shù)組的每個(gè)索引做為一個(gè)階梯，第i個(gè)階梯對(duì)應(yīng)著一個(gè)非負(fù)數(shù)的體力花費(fèi)值costi。

每當(dāng)你爬上一個(gè)階梯你都要花費(fèi)對(duì)應(yīng)的體力花費(fèi)值，然后你可以選擇繼續(xù)爬一個(gè)階梯或者爬兩個(gè)階梯。

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

示例 1:

輸入:cost = [10, 15, 20]

輸出:15

解釋:最低花費(fèi)是從cost[1]開始，然后走兩步即可到階梯頂，一共花費(fèi)15。

示例 2:

輸入:cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]

輸出:6

解釋:最低花費(fèi)方式是從cost[0]開始，逐個(gè)經(jīng)過那些1，跳過cost[3]，一共花費(fèi)6。

注意：

cost的長(zhǎng)度將會(huì)在[2, 1000]。

每一個(gè)cost[i] 將會(huì)是一個(gè)Integer類型，范圍為[0, 999]

class Solution:

    def minCostClimbingStairs(self, cost):

        """

        :type cost: List[int]

        :rtype: int

        """

        short_path_dict={}

        def f(index):  # index=0~len()-1

            if index < len(cost_dict) - 2:

                if not short_path_dict.__contains__(index):

                    short_path= min(

                        f(index + 1),

                        f(index + 2))

                    short_path_dict[index] = short_path+cost_dict[index]

                    return short_path+cost_dict[index]

                else:

                    return short_path_dict[index]#+cost_dict[index]

            else:

                short_path_dict[index]=cost_dict[index]

                return cost_dict[index]

   

        input_list = cost

        

        cost_dict = {}

        for ix, i in enumerate(input_list):

            cost_dict[ix] = int(i)

        

        return (min(f(0), f(1)))