746. 使用最小花费爬楼梯

🟢   🔖  数组 动态规划  🔗 力扣 LeetCode

题目

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

Input: cost = [10,15 ,20]

Output: 15

Explanation: You will start at index 1.

• Pay 15 and climb two steps to reach the top.

The total cost is 15.

Example 2:

Input: cost = [1 ,100,1 ,1,1 ,100,1 ,1 ,100,1]

Output: 6

Explanation: You will start at index 0.

• Pay 1 and climb two steps to reach index 2.
• Pay 1 and climb two steps to reach index 4.
• Pay 1 and climb two steps to reach index 6.
• Pay 1 and climb one step to reach index 7.
• Pay 1 and climb two steps to reach index 9.
• Pay 1 and climb one step to reach the top.

The total cost is 6.

Constraints:

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

题目大意

给你一个整数数组 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 <= cost.length <= 1000
• 0 <= cost[i] <= 999

解题思路

思路一：动态规划

可以使用动态规划，从后往前计算每个台阶到达楼顶的最小花费，最终取前两步中花费较小的值作为答案。

1. 定义状态：设 dp[i] 表示从第 i 个台阶爬到楼顶的最小花费。

2. 状态转移方程：要到达楼顶，可以从 i+1 或 i+2 号台阶爬上去：dp[i] = cost[i] + min(dp[i+1], dp[i+2])

3. 初始化：

• dp[n] = 0，表示从楼顶出发不需要额外花费。
• dp[n+1] = 0，是因为计算时需要多一个占位值，表示超过楼顶的情况。

4. 最终结果：起始点可以从第 0 或第 1 个台阶出发，所以答案为：min(dp[0], dp[1])

复杂度分析

• 时间复杂度：O(n)，遍历 cost 数组一次。
• 空间复杂度：O(n)，使用长度为 n + 2 的数组。

---

思路二：优化空间复杂度的动态规划

在上述代码中，使用了一个长度为 n + 2 的 dp 数组存储每个状态的值，但实际上，我们只需要关注 dp[i+1] 和 dp[i+2]。因此，可以使用滚动变量代替数组存储，降低空间复杂度。

复杂度分析

• 时间复杂度：O(n)，遍历 cost 数组一次。
• 空间复杂度：O(1)，仅使用两个滚动变量，空间复杂度降低为 O(1)。

代码

s 动态规划

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
	const n = cost.length;
	const dp = new Array(n + 2).fill(0); // 初始化 dp 数组
	for (let i = n - 1; i >= 0; i--) {
		// 从后向前计算
		dp[i] = cost[i] + Math.min(dp[i + 1], dp[i + 2]);
	}
	return Math.min(dp[0], dp[1]); // 返回从第 0 或第 1 步开始的最小花费
};

s 优化空间复杂度的动态规划

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
	const n = cost.length;
	let dp1 = 0,
		dp2 = 0; // 初始化 dp[i+1] 和 dp[i+2]
	for (let i = n - 1; i >= 0; i--) {
		const cur = cost[i] + Math.min(dp1, dp2); // 当前的 dp[i]
		dp2 = dp1; // 更新 dp[i+2]
		dp1 = cur; // 更新 dp[i+1]
	}
	return Math.min(dp1, dp2); // 返回从第 0 或第 1 步开始的最小花费
};

相关题目

题号	标题	题解	标签	难度	力扣
70	爬楼梯	[✓]	记忆化搜索 数学 动态规划	🟢	🀄️ 🔗
3154	到达第 K 级台阶的方案数		位运算 记忆化搜索 数学 2+	🔴	🀄️ 🔗