Min Cost Climbing Stairs

79.2k
0

An integer array cost is given, where cost[index] represents the price of stepping on stair index.

After paying the price of a stair, a 1-step jump or a 2-step jump can be taken. The climb may begin from stair 0 or stair 1.

Return the minimum total cost required to reach the top beyond the last stair.

Example 1

Input: cost = [10, 15, 20]
Output: 15
Explanation: Starting from stair 1 costs 15, and a 2-step jump reaches the top.

Example 2

Input: cost = [5, 10]
Output: 5
Explanation: Starting from stair 0 costs 5, and a 2-step jump reaches the top.

Recursion

Start with the smallest useful idea: reaching a stair can happen from only two previous places. A 1-step jump reaches the current stair from index - 1, and a 2-step jump reaches the current stair from index - 2.

The same choice appears again for every earlier stair. So recursion fits naturally. The state solve(index) stores the minimum cost needed to reach stair index.

The first helper call starts at n - 1, and the second helper call starts at n - 2, because either final stair can lead directly to the top. Each helper call moves backward through smaller indices.

Algorithm

  • Define solve(index) as the minimum cost to reach stair index, so every call represents one smaller stair problem.

  • Handle both base conditions together because stair 0 and stair 1 can serve as direct starting choices.

  • The cost from index - 1 is calculated because a 1-step jump can reach the current stair from the previous stair.

  • The cost from index - 2 is calculated because a 2-step jump can reach the current stair from two stairs behind.

  • The cheaper previous cost is selected because a minimum total cost is required.

  • The current stair cost is added because landing on the current stair must be paid.

  • The public method returns the minimum of solve(n - 1) and solve(n - 2) because the top can be reached from either final candidate stair.

Dry Run

Min Cost Climbing Stairs Recursion

Min Cost Climbing Stairs Recursion

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Finds a stair's minimum cost through recursion.
int solve(int index, vector<int>& cost) {
// A starting stair costs only the selected stair value.
if (index == 0 || index == 1) {
return cost[index];
}
// A 1-step jump comes from the previous stair.
int oneStepJump = solve(index - 1, cost);
// A 2-step jump comes from two stairs behind.
int twoStepJump = solve(index - 2, cost);
// Choose the cheaper path before paying the stair cost.
int bestPrevious = min(oneStepJump, twoStepJump);
return cost[index] + bestPrevious;
}
public:
// Returns the minimum cost required to reach the top.
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
// For two stairs, choose the cheaper starting cost.
if (n == 2) {
return min(cost[0], cost[1]);
}
// The top follows either of the final two stairs.
int lastStair = solve(n - 1, cost);
int secondLastStair = solve(n - 2, cost);
return min(lastStair, secondLastStair);
}
};
// Driver code
int main() {
vector<int> cost = {10, 15, 20};
Solution obj;
cout << obj.minCostClimbingStairs(cost);
return 0;
}

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Complexity Analysis

Time Complexity: O(2N), where N is the number of stairs, because each state can branch into two recursive calls and the same states may be recomputed multiple times.

Space Complexity: O(N), because the recursion stack can grow to a depth of at most N.

Memoization

Direct recursion feels clear, but the same stairs are solved again and again. For example, solve(2) can appear inside several larger calls. A small saved note for each index removes the repeated work.

Memoization keeps the same state, solve(index). The only new piece is a dp array. After the minimum cost for a stair is calculated once, the stored value is reused whenever the same stair appears again.

Algorithm

  • Create a dp array of size n filled with -1, so every untouched entry marks an uncalculated state.

  • Define solve(index) as the minimum cost to reach stair index, so the memoized state matches the recursive state.

  • Handle both base conditions together because stair 0 and stair 1 can serve as direct starting choices.

  • Return dp[index] after a cache hit because a stored answer removes the repeated recursive work.

  • Calculate costs from index - 1 and index - 2 because both jumps can reach the current stair.

  • Store the current answer in dp[index] so later calls can reuse the cheaper completed path.

  • The public method returns the minimum of solve(n - 1) and solve(n - 2) because the top can be reached from either final candidate stair.

Dry Run

Min Cost Climbing Stairs Memoization

Min Cost Climbing Stairs Memoization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Finds a stair's minimum cost with memoization.
int solve(int index, vector<int>& cost, vector<int>& dp) {
// A starting stair costs only the selected stair value.
if (index == 0 || index == 1) {
return cost[index];
}
// A calculated state is reused to avoid repeated recursion.
if (dp[index] != -1) {
return dp[index];
}
// A 1-step jump comes from the previous stair.
int oneStepJump = solve(index - 1, cost, dp);
// A 2-step jump comes from two stairs behind.
int twoStepJump = solve(index - 2, cost, dp);
// Choose the cheaper path before paying the stair cost.
int bestPrevious = min(oneStepJump, twoStepJump);
// Store the answer so later calls can reuse the result.
dp[index] = cost[index] + bestPrevious;
return dp[index];
}
public:
// Returns the minimum cost required to reach the top.
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n, -1);
// For two stairs, choose the cheaper starting cost.
if (n == 2) {
return min(cost[0], cost[1]);
}
// The top follows either of the final two stairs.
int lastStair = solve(n - 1, cost, dp);
int secondLastStair = solve(n - 2, cost, dp);
return min(lastStair, secondLastStair);
}
};
// Driver code
int main() {
vector<int> cost = {10, 15, 20};
Solution obj;
cout << obj.minCostClimbingStairs(cost);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of stairs, because each stair state is computed once and reused from the dp array.

Space Complexity: O(N), because the dp array stores one value for each stair and the recursion stack can contain up to N active calls.

Tabulation

Memoization still uses recursion. Tabulation turns the same idea into a small left-to-right table. Once the minimum cost for earlier stairs is known, the next stair can be filled directly.

The state stays unchanged: dp[index] stores the minimum cost needed to reach stair index. The first two stairs are direct starting choices. From index 2 onward, the cheaper of the previous two table values is used.

Algorithm

  • Create a dp array of size n so every stair keeps one minimum cost for later transitions.

  • The base values are initialized as dp[0] = cost[0] and dp[1] = cost[1] because both stairs can be chosen as starting points.

  • A loop is run from index 2 to n - 1 because every later stair depends on two earlier stairs.

  • Read dp[index - 1] because a 1-step jump reaches the current stair from the previous stair.

  • Read dp[index - 2] because a 2-step jump reaches the current stair from two stairs behind.

  • Fill the current table value with the cheaper previous cost plus cost[index] because landing on the current stair must be paid.

  • The minimum of dp[n - 1] and dp[n - 2] is returned because the top can be reached from either final candidate stair.

Dry Run

min-cost-climbing-stairs-tabulation.png

min-cost-climbing-stairs-tabulation.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the minimum cost required to reach the top.
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n, 0);
dp[0] = cost[0];
dp[1] = cost[1];
// Earlier values exist before each later stair.
for (int index = 2; index < n; index++) {
int oneStepJump = dp[index - 1];
int twoStepJump = dp[index - 2];
// Add the current cost to the cheaper previous path.
int bestPrevious = min(oneStepJump, twoStepJump);
dp[index] = cost[index] + bestPrevious;
}
// The top follows either of the final two stairs.
return min(dp[n - 1], dp[n - 2]);
}
};
// Driver code
int main() {
vector<int> cost = {10, 15, 20};
Solution obj;
cout << obj.minCostClimbingStairs(cost);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of stairs, because each stair from index 2 to N - 1 is processed exactly once.

Space Complexity: O(N), because the dp array stores one minimum-cost value for each stair, while the iterative approach uses no recursion stack.

Space Optimization

The tabulation table is helpful, but every new stair needs only the two previous values. Older entries stop being useful after the next value is calculated.

So previous2 represents dp[index - 2], and previous1 represents dp[index - 1]. For every current stair, current is calculated from both saved values, then variables are shifted forward in order.

Algorithm

  • Keep previous2 = cost[0] and previous1 = cost[1] so the first two DP states remain available without an array.

  • A loop is run from index 2 to n - 1 because each later stair needs the two previous DP values.

  • The cheaper of previous1 and previous2 is selected because the current stair can be reached by a 1-step jump or a 2-step jump.

  • Calculate current from the cheaper previous value plus cost[index] because the current stair must be paid.

  • The variable previous2 is shifted to previous1 because the old previous stair becomes two stairs behind for the next index.

  • The variable previous1 is shifted to current because the current stair becomes the previous stair for the next index.

  • The minimum of previous1 and previous2 is returned because the top can be reached from either final candidate stair.

Dry Run

min-cost-climbing-stairs-space-optimization.png

min-cost-climbing-stairs-space-optimization.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the minimum cost required to reach the top.
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
int previous2 = cost[0];
int previous1 = cost[1];
// Later stairs only require the two previous minimum costs.
for (int index = 2; index < n; index++) {
// The current value adds cost to the cheaper path.
int bestPrevious = min(previous1, previous2);
int current = cost[index] + bestPrevious;
// Shift values to retain the latest two states.
previous2 = previous1;
previous1 = current;
}
// The top follows either of the final two stairs.
return min(previous1, previous2);
}
};
// Driver code
int main() {
vector<int> cost = {10, 15, 20};
Solution obj;
cout << obj.minCostClimbingStairs(cost);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of stairs, because each stair from index 2 to N - 1 is processed exactly once.

Space Complexity: O(1), because only previous2, previous1, current, and a few scalar variables are maintained while older DP states are discarded.

Interview follow-up Questions

The problem allows either starting stair, so the starting choice has no movement cost before landing. The paid value begins with the selected starting stair.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Given an array nums containing distinct positive integers, return a maximum-length subset. For every pair of values first and second in the subset, either first % second == 0 or second % first == 0...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

An array prices stores a stock price for each day, and an integer fee gives the cost of one completed transaction. Any number of transactions may be completed, but only one share may...

65.7k
Dynamic Programming

Check If a Subset with the Target Sum Exists

Given an array arr containing n positive integers and a non-negative integer target , select each array position at most once. Return true if the sum of selected elements equals target ; otherwise,...

55.1k
Comments0