On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

在楼梯上，第i步有一些非负成本成本[i]分配（0索引）。

一旦支付了费用，您可以爬一到两步。 您需要找到到达楼层顶部的最低成本，您可以从索引为0的步骤开始，也可以从索引为1的步骤开始。

Example 1:

Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

Example 2:

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

Note:

1. cost will have a length in the range [2, 1000].
2. Every cost[i] will be an integer in the range [0, 999].

python实践

class Solution:
    def minCostClimbingStairs(self, cost):
        # dp存放到达每一层的花费值
        costed = [0, 0]
        for i in range(2, len(cost)):
            costed.append(min(costed[i - 1] + cost[i - 1], costed[i - 2] + cost[i - 2]))
        return min(costed[-1] + cost[-1], costed[-2] + cost[-2])

if __name__ == '__main__':
    t = Solution().minCostClimbingStairs(cost=[1, 100, 1, 1, 1, 100, 1, 1, 100, 1])
    print(t)

自己不会写

网上思路：

• https://blog.csdn.net/Next_Second/article/details/78861839