leetcode代码记录（使用最小花费爬楼梯

1. 题目：

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

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

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

示例 1：

输入：cost = [10,15,20]

输出：15

解释：你将从下标为 1 的台阶开始。

• 支付 15 ，向上爬两个台阶，到达楼梯顶部。
  总花费为 15 。

示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]

输出：6

解释：你将从下标为 0 的台阶开始。

• 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
• 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
• 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
• 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
• 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
• 支付 1 ，向上爬一个台阶，到达楼梯顶部。
  总花费为 6 。

2. 我的代码：

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

        # 定义dp数组
        dp = [0] * (len(cost) + 1)

        # 初始
        dp[0] = 0
        dp[1] = 0

        # 递推关系
        for i in range(2, len(cost) + 1):
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
            print(dp[i])
        
        return dp[len(cost)]

动态规划最重要最需要理清楚的点：

1. dp数组及其下标的含义
2. 递推公式
3. dp数组初始化
4. 遍历顺序

这里，通过推理得到：

1. dp下标代表的是第几个台阶，dp数组的值代表到达该台阶的最小花费
2. 递推公式即是：当前两个台阶到达该台阶的最小值，由于支付的费用是前一个台阶的费用cost，所以递推公式为dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
3. dp数组初始化，由于至少要用到两个，所以我们把前两个初始化一下，dp[0]当然是0，dp[1]是从0或者-1跳上来的，由于0处一定会付费，所以最小值一定是直接从-1跳上来，即dp[1] = 0
4. 遍历顺序，这里是从3到len(cost)

排除特殊情况时一定要画图检查一下，到底怎么排除，排除得到的结果是什么，别死在这上面