746. 使用最小花费爬楼梯 Easy

给你一个整数数组 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 。

解题思路

输入： 一个整数数组代表每个台阶需要支付的费用

输出： 每次可以爬 1 或 2 个台阶，爬到楼顶的最低花费

本题属于线性DP问题。

定义状态

dp[i] 表示爬到第 i 层需要的最小花费

状态转移

达到第 i 层我们可以有两种方式：

• 从 i - 1 跨一步过来：代价是 dp[i - 1] + cost[i - 1]
• 从 i - 2 跨两步过来：代价是 dp[i - 2] + cost[i - 2]

所以状态转移方程是： dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

最终答案是 dp[n]

代码实现

python

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # 获取楼梯的长度
        n = len(cost)
        # 创建一个数组dp，用于存储到达每个台阶的最小花费
        # 数组长度为n+1，因为可以选择从第n个台阶跳到终点
        dp = [0] * (n + 1)

        # 从第2个台阶开始计算（因为dp[0]和dp[1]初始为0）
        for i in range(2, n + 1):
            # 计算到达第i个台阶的最小花费
            # 可以从i-1台阶跳一步（花费cost[i-1]）或从i-2台阶跳两步（花费cost[i-2]）
            # 取两者中的较小值
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
        
        # 返回到达终点（第n个台阶）的最小花费
        return dp[n]

javascript

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
    const dp = Array(cost.length + 1).fill(0);

    for (let i = 2; i < cost.length + 1; i++) {
        dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }

    return dp[cost.length];
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

746 国际版

746 中文版