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)]
动态规划最重要最需要理清楚的点：
- dp数组及其下标的含义
- 递推公式
- dp数组初始化
- 遍历顺序
这里，通过推理得到：
- dp下标代表的是第几个台阶，dp数组的值代表到达该台阶的最小花费
- 递推公式即是：当前两个台阶到达该台阶的最小值，由于支付的费用是前一个台阶的费用cost，所以递推公式为dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
- dp数组初始化，由于至少要用到两个，所以我们把前两个初始化一下，dp[0]当然是0，dp[1]是从0或者-1跳上来的，由于0处一定会付费，所以最小值一定是直接从-1跳上来，即dp[1] = 0
- 遍历顺序，这里是从3到len(cost)
排除特殊情况时一定要画图检查一下，到底怎么排除，排除得到的结果是什么，别死在这上面
