class Solution:
def minCostClimbingStairs(self , cost: List[int]) -> int:
# write code here

# 动态规划
# 1、确定状态
# 最后一步前必定是在第i-1级台阶 或 第i-2级台阶
# 原问题：求通过第i级台阶所花费的最少代价
# 子问题：求通过第i-1级台阶和通过第i-2级台阶之间花费的最少代价
# 2、转移方程
# f(i) = min {f(i-1)+cost(i-1), f(i-2)+cost(i-2)}
# 3、初始条件
# 因为可以选择直接从台阶0或台阶1开始爬楼梯，所以: f(0)=0, f(1)=0
# 4、计算顺序
# 从小到大依次计算
# 5、编程实现
n = len(cost) # 有n级台阶
f = [0]*(n+1) # 台阶从0开始，所以索引n为楼梯顶部，即有n+1级台阶
for i in range(2, n+1): # 按从小到大的顺序计算
f[i] = min(f[i-1]+cost[i-1], f[i-2]+cost[i-2])
return f[n]

给定一个整数数组 cost \cost ，其中 cost[i]\cost[i] 是从楼梯第i \i 个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。