class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
}
};
746. 使用最小花费爬楼梯
给你一个整数数组 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 <= 10000 <= cost[i] <= 999相似题目
原站题解
cpp 解法, 执行用时: 8 ms, 内存消耗: 13.8 MB, 提交时间: 2023-12-17 00:10:59
class Solution {
public:
int minCostClimbingStairs1(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n + 1);
dp[0] = dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
int prev = 0, curr = 0;
for (int i = 2; i <= n; i++) {
int next = min(curr + cost[i - 1], prev + cost[i - 2]);
prev = curr;
curr = next;
}
return curr;
}
};
python3 解法, 执行用时: 44 ms, 内存消耗: 16.1 MB, 提交时间: 2023-12-17 00:10:32
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
n = len(cost)
prev = curr = 0
for i in range(2, n + 1):
nxt = min(curr + cost[i - 1], prev + cost[i - 2])
prev, curr = curr, nxt
return curr
golang 解法, 执行用时: 0 ms, 内存消耗: 2.7 MB, 提交时间: 2023-12-17 00:10:13
func minCostClimbingStairs(cost []int) int {
n := len(cost)
pre, cur := 0, 0
for i := 2; i <= n; i++ {
pre, cur = cur, min(cur+cost[i-1], pre+cost[i-2])
}
return cur
}
func min(a, b int) int { if a < b { return a }; return b }
javascript 解法, 执行用时: 72 ms, 内存消耗: 41.8 MB, 提交时间: 2023-12-17 00:09:40
/**
* @param {number[]} cost
* @return {number}
*/
var minCostClimbingStairs = function(cost) {
const n = cost.length;
const dp = new Array(n + 1);
dp[0] = dp[1] = 0;
for (let i = 2; i <= n; i++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
};
var minCostClimbingStairs2 = function(cost) {
const n = cost.length;
let prev = 0, curr = 0;
for (let i = 2; i <= n; i++) {
let next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
prev = curr;
curr = next;
}
return curr;
};
java 解法, 执行用时: 0 ms, 内存消耗: 42.2 MB, 提交时间: 2023-12-17 00:09:14
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int prev = 0, curr = 0;
for (int i = 2; i <= n; i++) {
int next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
prev = curr;
curr = next;
}
return curr;
}
}
java 解法, 执行用时: 0 ms, 内存消耗: 41.7 MB, 提交时间: 2023-12-17 00:09:03
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[] dp = new int[n + 1];
dp[0] = dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}
}
python3 解法, 执行用时: 40 ms, 内存消耗: 14.9 MB, 提交时间: 2022-07-18 10:16:37
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
n = len(cost)
dp = [0] * (n + 1)
for i in range(2, n+1):
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
return dp[n]
golang 解法, 执行用时: 4 ms, 内存消耗: 3 MB, 提交时间: 2021-07-17 12:11:02
func minCostClimbingStairs(cost []int) int {
n := len(cost)
dp := make([]int, n+1)
for i := 2; i <= n; i++ {
dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
}
return dp[n]
}
func min(x, y int) int {
if x > y {
return y
}
return x
}