class Solution:
    def minCostClimbingStairs(self , cost: List[int]) -> int:
        dp = [0 for i in range(len(cost)+1)]
        for i in range(2, len(cost)+1):
            dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])

        return dp[-1]

解题思路

• 先构建一个长度为cost长度+1的数组（0-n）；
• 循环计算到每一个阶梯最小的花费是什么，得到转移状态方程，即dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])。

复杂度

时间复杂度为O（N），空间复杂度为O（N）。