# 746. Min Cost Climbing Stairs

On a staircase, the `i`-th step has some non-negative cost `cost[i]` assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Example 1:

``````Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.
``````

Example 2:

``````Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].
``````

Note:

1. `cost` will have a length in the range `[2, 1000]`.
2. Every `cost[i]` will be an integer in the range `[0, 999]`.

dp[i] = min(dp[i- 2] + cost[i - 2], dp[i - 1] + cost[i - 1])

``````class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n + 1);
for (int i = 2; i < n + 1; ++i) {
dp[i] = min(dp[i- 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
}
return dp.back();
}
};
``````

dp[i] = cost[i] + min(dp[i- 1], dp[i - 2])

``````class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n);
dp[0] = cost[0]; dp[1] = cost[1];
for (int i = 2; i < n; ++i) {
dp[i] = cost[i] + min(dp[i- 1], dp[i - 2]);
}
return min(dp[n - 1], dp[n - 2]);
}
};
``````

``````class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int a = 0, b = 0;
for (int num : cost) {
int t = min(a, b) + num;
a = b;
b = t;
}
return min(a, b);
}
};
``````

``````class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
unordered_map<int, int> memo;
return helper(cost, cost.size(), memo);
}
int helper(vector<int>& cost, int i, unordered_map<int, int>& memo) {
if (memo.count(i)) return memo[i];
if (i <= 1) return memo[i] = cost[i];
return memo[i] = (i == cost.size() ? 0 : cost[i]) + min(helper(cost, i - 1, memo), helper(cost, i - 2, memo));
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/746

Climbing Stairs

https://leetcode.com/problems/min-cost-climbing-stairs/

https://leetcode.com/problems/min-cost-climbing-stairs/discuss/110109/c-o1-space

https://leetcode.com/problems/min-cost-climbing-stairs/discuss/110111/javascript-and-c-solutions

https://leetcode.com/problems/min-cost-climbing-stairs/discuss/144682/3-Lines-Java-Solution-O(1)-space

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation