Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Min Cost Climbing Stairs solution and explanation

EasyArrayDynamic Programming7 min read68.7% acceptanceUpdated 9 Apr 2026
Asked atSquarepoint CapitalGoogleAmazonMicrosoftMetaBloomberg
+1 moreTCS
Practise Min Cost Climbing Stairs
19:27
Min Cost Climbing Stairs - Dynamic Programming - Leetcode 746 - PythonNeetCode · 19:27 · 185K viewsWatch on YouTube
9 more videos on this problem
  1. Min Cost Climbing Stairs - Dynamic Programming - Leetcode 746 - PythonNeetCode · 19:27 · 185K views
  2. LeetCode Min Cost Climbing Stairs Solution Explained - JavaNick White · 10:20 · 34K views
  3. Min Cost Climbing Stairs - Leetcode 746 - Dynamic Programming (Python)Greg Hogg · 13:14 · 16K views
  4. Min Cost Climbing Stairs (LeetCode 746) | Full solution with thought process and animationsNikhil Lohia · 18:42 · 12K views
  5. Min Cost Climbing Stairs | Bottom Up | Recursion | Memoization | GOOGLE | Leetcode - 746codestorywithMIK · 23:58 · 11K views
  6. Min Cost Climbing Stairs 🚀 Leetcode 746 Hello World by Prince: Dynamic Programming TutorialHello World · 22:55 · 7K views
  7. Leetcode 746. Min Cost Climbing StairsFraz · 18:25 · 7K views
  8. 花花酱 LeetCode 746. Min Cost Climbing Stairs - 刷题找工作 EP137Hua Hua · 12:34 · 6K views
  9. Min Cost Climbing Stairs | Leetcode 746 | Live Coding SessionCoding Decoded · 6:40 · 4K views
  10. Min Cost Climbing Stairs - LeetCode #746 with python programmingCodingNinja · 8:54 · 4K views

The problem

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

Approach overview

Problem Overview: You are given an array cost where cost[i] represents the cost of stepping on the i-th stair. You can climb either one or two steps at a time, and you may start from step 0 or step 1. The goal is to reach the top of the staircase (one step beyond the last index) with the minimum total cost.

Approach 1: Dynamic Programming with Table (O(n) time, O(n) space)

This approach models the problem using dynamic programming. Define dp[i] as the minimum cost required to reach step i. Since you can arrive at step i from either i-1 or i-2, the recurrence becomes dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). Start with dp[0] = 0 and dp[1] = 0 because you can begin from either step without paying a cost. Iterate through the array, computing the optimal cost for each position until you reach the top. This approach clearly shows the subproblem structure and is easy to reason about during interviews. Time complexity is O(n) because each step is processed once, and space complexity is O(n) for the DP table.

Approach 2: Optimized Dynamic Programming with Constant Space (O(n) time, O(1) space)

The transition only depends on the previous two states, so storing the entire DP table is unnecessary. Track just two variables representing the minimum cost to reach the previous two steps. For each new step, compute the current minimum using the same recurrence: current = min(prev1 + cost[i-1], prev2 + cost[i-2]). Then shift the variables forward for the next iteration. This reduces memory usage while preserving the same logic as the table-based solution. The algorithm still iterates once through the input array, giving O(n) time complexity and O(1) extra space.

The key insight is recognizing overlapping subproblems. The minimum cost to reach a step depends only on the two steps before it, which makes the problem a classic dynamic programming pattern similar to Fibonacci-style state transitions.

Recommended for interviews: Start by explaining the DP state definition and recurrence using the table approach. It demonstrates that you understand how to break the problem into subproblems. Then optimize the solution by keeping only the last two states to achieve constant space. Interviewers typically expect the O(n) time and O(1) space dynamic programming solution.

Approach 1: Dynamic Programming with Table

This approach uses a dynamic programming table to store the minimum cost at each step. The key idea is that to reach step i, you can come from step i-1 or step i-2, and you need to pay the cost associated with landing on step i. Thus, the cost to reach step i is the minimum of the cost to reach steps i-1 or i-2 plus cost[i]. The solution returns the minimum cost to reach the top from the last two steps.

def minCostClimbingStairs(cost):
    n = len(cost)
    dp = [0] * (n + 1)
    dp[0], dp[1] = cost[0], cost[1]
    for i in range(2, n):
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
    return min(dp[n - 1], dp[n - 2])
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < n; i++) {
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        return Math.min(dp[n - 1], dp[n - 2]);
    }
}
#include <vector>
#include <algorithm>
using namespace std;

int minCostClimbingStairs(vector<int>& cost) {
    vector<int> dp(cost.size() + 1);
    dp[0] = cost[0];
    dp[1] = cost[1];
    for (int i = 2; i < cost.size(); i++) {
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    return min(dp[cost.size() - 1], dp[cost.size() - 2]);
}
var minCostClimbingStairs = function(cost) {
    const n = cost.length;
    const dp = new Array(n + 1);
    dp[0] = cost[0];
    dp[1] = cost[1];
    for (let i = 2; i < n; i++) {
        dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    return Math.min(dp[n - 1], dp[n - 2]);
};
#include <stdio.h>
#include <stdlib.h>

int minCostClimbingStairs(int* cost, int costSize) {
    int *dp = (int*)malloc((costSize + 1) * sizeof(int));
    dp[0] = cost[0];
    dp[1] = cost[1];
    for (int i = 2; i < costSize; i++) {
        dp[i] = (dp[i-1] < dp[i-2] ? dp[i-1] : dp[i-2]) + cost[i];
    }
    int result = dp[costSize-1] < dp[costSize-2] ? dp[costSize-1] : dp[costSize-2];
    free(dp);
    return result;
}
public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        int n = cost.Length;
        int[] dp = new int[n + 1];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < n; i++) {
            dp[i] = Math.Min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        return Math.Min(dp[n - 1], dp[n - 2]);
    }
}

This Python implementation creates a list dp to store minimum costs. The loop updates this list based on the minimum of the previous two costs plus the current step's cost. The return value is the minimum of the last two computed costs.

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor

Approach 2: Optimized Dynamic Programming with Constant Space

This approach optimizes the space usage of the dynamic programming solution by only retaining two variables to store the minimal costs for the last two steps, instead of an entire table. This is possible because each step's cost only depends on the previous two calculations. You update these two variables iteratively to find the minimum cost to reach the top.

def minCostClimbingStairs(cost):
    prev, curr = cost[0], cost[1]
    for i in range(2, len(cost)):
        prev, curr = curr, min(prev, curr) + cost[i]
    return min(prev, curr)
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int prev = cost[0];
        int curr = cost[1];
        for (int i = 2; i < cost.length; i++) {
            int next = Math.min(prev, curr) + cost[i];
            prev = curr;
            curr = next;
        }
        return Math.min(prev, curr);
    }
}
#include <vector>
using namespace std;

int minCostClimbingStairs(vector<int>& cost) {
    int prev = cost[0], curr = cost[1];
    for (int i = 2; i < cost.size(); ++i) {
        int next = min(prev, curr) + cost[i];
        prev = curr;
        curr = next;
    }
    return min(prev, curr);
}
var minCostClimbingStairs = function(cost) {
    let prev = cost[0], curr = cost[1];
    for (let i = 2; i < cost.length; i++) {
        let next = Math.min(prev, curr) + cost[i];
        prev = curr;
        curr = next;
    }
    return Math.min(prev, curr);
};
#include <stdio.h>

int minCostClimbingStairs(int* cost, int costSize) {
    int prev = cost[0];
    int curr = cost[1];
    for (int i = 2; i < costSize; i++) {
        int next = (prev < curr ? prev : curr) + cost[i];
        prev = curr;
        curr = next;
    }
    return (prev < curr ? prev : curr);
}
public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        int prev = cost[0], curr = cost[1];
        for (int i = 2; i < cost.Length; i++) {
            int next = Math.Min(prev, curr) + cost[i];
            prev = curr;
            curr = next;
        }
        return Math.Min(prev, curr);
    }
}

In the Python solution, the use of only two variables, prev and curr, represents a space-optimized calculation of minimum cost. The loop swaps and updates these variables iteratively. The final answer is determined by comparing the last values of these two variables.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Memoization Search

We design a function dfs(i), which represents the minimum cost required to climb the stairs starting from the i-th step. Therefore, the answer is min(dfs(0), dfs(1)).

The execution process of the function dfs(i) is as follows:

  • If i \ge len(cost), it means the current position has exceeded the top of the stairs, and there is no need to climb further, so return 0;
  • Otherwise, we can choose to climb 1 step with a cost of cost[i], then recursively call dfs(i + 1); or we can choose to climb 2 steps with a cost of cost[i], then recursively call dfs(i + 2);
  • Return the minimum cost between these two options.

To avoid repeated calculations, we use memoization search, saving the results that have already been calculated in an array or hash table.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array cost.

function minCostClimbingStairs(cost: number[]): number {
    const n = cost.length;
    const f: number[] = Array(n + 1).fill(0);
    for (let i = 2; i <= n; ++i) {
        f[i] = Math.min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
    }
    return f[n];
}
func minCostClimbingStairs(cost []int) int {
	n := len(cost)
	f := make([]int, n+1)
	for i := 2; i <= n; i++ {
		f[i] = min(f[i-1]+cost[i-1], f[i-2]+cost[i-2])
	}
	return f[n]
}
impl Solution {
    pub fn min_cost_climbing_stairs(cost: Vec<i32>) -> i32 {
        let n = cost.len();
        let mut f = vec![0; n + 1];
        for i in 2..=n {
            f[i] = std::cmp::min(f[i - 2] + cost[i - 2], f[i - 1] + cost[i - 1]);
        }
        f[n]
    }
}
Try this approach in the editor

Approach 4: Dynamic Programming

We define f[i] as the minimum cost needed to reach the i-th stair. Initially, f[0] = f[1] = 0, and the answer is f[n].

When i \ge 2, we can reach the i-th stair directly from the (i - 1)-th stair with one step, or from the (i - 2)-th stair with two steps. Therefore, we have the state transition equation:

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

The final answer is f[n].

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array cost$.

function minCostClimbingStairs(cost: number[]): number {
    const n = cost.length;
    const f: number[] = Array(n + 1).fill(0);
    for (let i = 2; i <= n; ++i) {
        f[i] = Math.min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
    }
    return f[n];
}
func minCostClimbingStairs(cost []int) int {
	n := len(cost)
	f := make([]int, n+1)
	for i := 2; i <= n; i++ {
		f[i] = min(f[i-1]+cost[i-1], f[i-2]+cost[i-2])
	}
	return f[n]
}
impl Solution {
    pub fn min_cost_climbing_stairs(cost: Vec<i32>) -> i32 {
        let n = cost.len();
        let mut f = vec![0; n + 1];
        for i in 2..=n {
            f[i] = std::cmp::min(f[i - 2] + cost[i - 2], f[i - 1] + cost[i - 1]);
        }
        f[n]
    }
}
Try this approach in the editor

Approach 5: Dynamic Programming (Space Optimization)

We notice that the state transition equation for f[i] only depends on f[i - 1] and f[i - 2]. Therefore, we can use two variables f and g to alternately record the values of f[i - 2] and f[i - 1], thus optimizing the space complexity to O(1).

function minCostClimbingStairs(cost: number[]): number {
    let [f, g] = [0, 0];
    for (let i = 1; i < cost.length; ++i) {
        [f, g] = [g, Math.min(f + cost[i - 1], g + cost[i])];
    }
    return g;
}
func minCostClimbingStairs(cost []int) int {
	var f, g int
	for i := 2; i <= n; i++ {
		f, g = g, min(f+cost[i-2], g+cost[i-1])
	}
	return g
}
impl Solution {
    pub fn min_cost_climbing_stairs(cost: Vec<i32>) -> i32 {
        let (mut f, mut g) = (0, 0);
        for i in 2..=cost.len() {
            let gg = std::cmp::min(f + cost[i - 2], g + cost[i - 1]);
            f = g;
            g = gg;
        }
        g
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Dynamic Programming with Table

Time Complexity: O(n)
Space Complexity: O(n)

Optimized Dynamic Programming with Constant Space

Time Complexity: O(n)
Space Complexity: O(1)

Memoization Search–
Dynamic Programming–
Dynamic Programming (Space Optimization)–

Complexity analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with TableO(n)O(n)When learning or explaining DP state transitions clearly in interviews
Optimized Dynamic Programming (Constant Space)O(n)O(1)Preferred production and interview solution when memory optimization matters

Frequently asked questions

Is Min Cost Climbing Stairs easy or hard?

LeetCode classifies Min Cost Climbing Stairs as an Easy problem. The logic becomes straightforward once you recognize the dynamic programming pattern where each step depends on the previous two states.

Min Cost Climbing Stairs Python/Java solution

Python and Java implementations typically use dynamic programming. The optimized solution maintains two variables representing the minimum cost for the last two steps and iterates through the array once, achieving O(n) time and O(1) space.

How to solve Min Cost Climbing Stairs in O(n)?

Iterate through the cost array while maintaining the minimum cost to reach the previous two steps. For each step, compute the new minimum using min(prev1 + cost[i-1], prev2 + cost[i-2]). Continue until reaching the top of the staircase. This dynamic programming approach processes the array once, giving O(n) time.

What is the best approach for Min Cost Climbing Stairs?

The best approach uses dynamic programming with constant space. Track the minimum cost to reach the previous two steps and compute the current cost using a recurrence relation. This solution runs in O(n) time and O(1) space, making it both efficient and interview-friendly.

Is Min Cost Climbing Stairs asked at Google/Amazon/Meta?

Min Cost Climbing Stairs is a common dynamic programming interview problem and has appeared in coding interviews at companies like Amazon and Google. It tests understanding of DP state transitions and optimization from O(n) space to O(1) space.

What data structure is used in Min Cost Climbing Stairs?

The primary technique is dynamic programming applied to an array. The DP table stores the minimum cost to reach each step. In the optimized version, only two variables are needed instead of a full array.

What is the time complexity of Min Cost Climbing Stairs?

The optimal solution runs in O(n) time because each stair is processed exactly once. Dynamic programming avoids recomputation by storing or tracking previous results. Space complexity can be O(n) with a DP table or optimized to O(1) using two variables.

Comments

Next problem · similarClimbing StairsEasy
Now write it yourselfClose this page and solve Min Cost Climbing Stairs in the editor, without looking.
Practise Min Cost Climbing Stairs