题目难度: 简单
今天继续更新 Leetcode 的剑指 Offer（专项突击版）系列, 大家在公众号 算法精选 里回复
剑指offer2就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
数组的每个下标作为一个阶梯，第 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 <= 1000
- 0 <= cost[i] <= 999
题目思考
- 第 n 个阶梯的最低花费可以根据什么得出?
解决方案
- 这个题目非常类似之前剑指 Offer 系列的(青蛙跳台阶问题), 只是那道题目是求总方案数, 而这里是求最小花费, 感兴趣的同学可以先看看那篇文章, 然后举一反三, 尝试自己解答
- 分析题目, 每次要么跳 1 级, 要么跳 2 级, 也就是相邻台阶之间的关系非常明确, 可以尝试动态规划的思路
- 对于第 n 个阶梯来说, 它可以从 n-1 阶跳 1 级得到, 也可以由 n-2 阶跳 2 级得到, 自然第 n 阶的最小花费就是 n-1 阶和 n-2 阶的最小花费的较小值, 再加上跳到第 n 阶的花费
- 用数学语言来表示: 假设
dp[n]代表到达第 n 个阶梯的最低花费, 那么就有dp[n]=min(dp[n-1], dp[n-2])+cost[n], 另外开始时可以选择下标 0 或 1 作为初始阶梯, 所以初始化dp[0]=cost[0],dp[1]=cost[1] - 由于当前 dp 值只和前面两个 dp 值有关, 所以我们可以只使用两个变量
pre和ppre, 分别代表当前下标的前一个和更前一个下标的 dp 值dp[n-1]和dp[n-2]. - 然后当前的 dp 值就更新为它们两个的较小值加上当前花费
- 最后更新
ppre和pre, 分别更新为旧的pre和当前 dp 值, 用于下一个 dp 值的计算 - 而最终结果就是
ppre和pre的较小值, 因为楼顶可以从倒数第一阶或倒数第二阶上去 - 下面的代码中有详细的注释, 方便大家理解
复杂度
- 时间复杂度
O(N): 需要遍历整个数组一遍 - 空间复杂度
O(1): 只需要几个常数空间的变量
代码
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
# 初始化ppre和pre为第0和第1阶梯的花费
ppre, pre = cost[0], cost[1]
for c in cost[2:]:
# 当前dp值是ppre和pre的较小值再加上当前花费
# 然后滚动更新ppre和pre
ppre, pre = pre, min(ppre, pre) + c
# 最终结果是倒数第二阶或倒数第一阶的最小花费的较小值
return min(ppre, pre)
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号