爬楼梯

题目要求 输入输出 输入：整数 n 含义：爬到第 n 阶楼顶 每次可以爬 1 或 2 阶 输出：返回到达楼顶的不同走法数量 约束：1 <= n <= 45 示例 输入：n = 2 输出：2 解释：1+1，2 输入：n = 3 输出：3 解释：1+1+1，1+2，2+1 这篇只用 Python，从 dp[i] 的含义一步一步推出最终代码。 从 n = 3 的最后一步开始 先看最小能暴露转移的例子： n = 3 到第 3 阶的最后一步只可能来自： 第 2 阶，再走 1 阶 第 1 阶，再走 2 阶 所以“到第 3 阶的方法数”不是凭空算出来的，而是来自两个更小的位置。 Step 1：先定义更小的问题 直接问“到第 n 阶有几种走法”太大。先定义： dp[i] = 到达第 i 阶的方法数 注意这里的 i 是楼梯位置，不是数组下标含义上的第几个元素。 ...

题目要求 输入输出 输入：整数数组 cost cost[i] 表示踩到第 i 阶的代价 每次可以爬 1 或 2 阶 可以从下标 0 或下标 1 开始 输出：返回到达楼顶的最小花费 约束：2 <= cost.length <= 1000，0 <= cost[i] <= 999 示例 输入：cost = [10,15,20] 输出：15 解释：从下标 1 开始，付 15 后直接到达 top 输入：cost = [1,100,1,1,1,100,1,1,100,1] 输出：6 从 [10,15,20] 的 top 位置开始 先看最小例子： cost = [10,15,20] 楼顶不是下标 2，而是在最后一阶之后的位置，可以记为位置 3。 到达 top 位置 3 的最后一步只可能来自： 位置 2，付 cost[2] 位置 1，付 cost[1] 这题最容易错的地方就在这里：我们要求的是“到达 top 的花费”，不是“到达最后一个下标的花费”。 ...