难度: Easy
数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。
请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
示例 1：
输入：cost = [10, 15, 20] 输出：15 解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。
示例 2：
输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出：6 解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。
提示：
2 <= cost.length <= 10000 <= cost[i] <= 999注意：本题与主站 746 题相同： https://leetcode-cn.com/problems/min-cost-climbing-stairs/
运行时间: 22 ms
内存: 16.1 MB
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
a = b = 0
for i in range(2, len(cost)+1):
c = min(a+cost[i-2], b+cost[i-1])
a = b
b = c
return b
这个题解采用了动态规划的方法。定义两个变量a和b来存储到达每一步时的最小花费。变量a存储到达前一个阶梯的最小花费，变量b存储到达当前阶梯的最小花费。对于每一个阶梯i，可以从i-1或i-2阶梯到达，因此到达i阶梯的最小花费可以从这两种情况中取较小值，即c = min(a + cost[i-2], b + cost[i-1])。然后更新变量a和b的值为下一轮的前两个花费，即a = b和b = c。这样，当迭代完成后，b存储的就是达到楼顶的最小花费。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
a = b = 0 # 初始化前两步的最小花费
for i in range(2, len(cost)+1):
c = min(a+cost[i-2], b+cost[i-1]) # 计算到达当前步的最小花费
a = b # 更新前一步的花费
b = c # 更新当前步的花费
return b # 返回最终达到楼顶的最小花费
这是因为题目规定了每次只能爬一阶或两阶楼梯，所以从i-1或i-2到达i是唯一可能的两种方式。如果考虑从其他步数到达i，那将违反题目的基本规定，导致解法不适用。动态规划的设计需要严格根据问题的约束来设定状态转移方程。
变量a和b初始化为0的原因在于题目允许从第0级或第1级阶梯开始爬楼梯，且不需要支付这两个阶梯的成本作为初始条件。这样，a和b作为动态规划中的初始状态，对应于达到这两个阶梯的累计最小花费（在开始爬楼梯前没有花费）。这是一个典型的边界条件设置，确保了无论从哪一步开始，算法都能正确计算出从起点开始的最低成本。
确实如此。在迭代到len(cost)+1时，实际上考虑的是到达楼梯顶端之后的虚拟位置。这种设计允许算法计算在最后一步完全踏上楼顶需要的最小花费。因为可以从最后一个或倒数第二个阶梯一步到达楼顶，所以需要将迭代延伸到cost数组长度之外，以便涵盖所有可能的最终步骤。