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 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。