746. Min Cost Climbing Stairs - Explanation

Description

You are given an array of integers cost where cost[i] is the cost of taking a step from the ith floor of a staircase. After paying the cost, you can step to either the (i + 1)th floor or the (i + 2)th floor.

You may choose to start at the index 0 or the index 1 floor.

Return the minimum cost to reach the top of the staircase, i.e. just past the last index in cost.

Example 1:

Input: cost = [1,2,3]

Output: 2

Explanation: We can start at index = 1 and pay the cost of cost[1] = 2 and take two steps to reach the top. The total cost is 2.

Example 2:

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

Output: 4

Explanation: Start at index = 0.

Pay the cost of cost[0] = 1 and take two steps to reach index = 2.
Pay the cost of cost[2] = 1 and take two steps to reach index = 4.
Pay the cost of cost[4] = 1 and take two steps to reach index = 6.
Pay the cost of cost[6] = 1 and take one step to reach the top.
The total cost is 4.

Constraints:

2 <= cost.length <= 100
0 <= cost[i] <= 100

Topics

Array Dynamic Programming

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the number of steps on the staircase.

Hint 1

Can you find the recurrence relation to solve the problem, given that at each step we have two options: going one step or two steps? Consider drawing a decision tree where we branch into two paths at each step. By exploring every path, we can get the minimum cost. However, this results in an O(2^n) time solution. Can you think of a better approach? Is there any repeated work in the decision tree that we can optimize?

Hint 2

The recurrence relation can be expressed as cost[i] + min(dfs(i + 1), dfs(i + 2)), where i is the current position and dfs is the recursive function. To avoid recalculating the result of a recursive call multiple times, we can use Memoization. Initialize a cache array of size n, where n is the number of steps on the staircase. How would you implement this?

Hint 3

We start the recursion from positions 0 and 1. At each recursive step, before computing the result, we check if the result for the current position has already been calculated. If it has, we return the stored value. Otherwise, we calculate the result for the current position, store it in the cache, and then return the result. What can be the base condition for this recursion to stop?

Hint 4

The base condition would be to return 0 if we are at the top of the staircase i >= n. This is a one-dimensional dynamic programming problem. We can further optimize the memoization solution by using advanced techniques such as Bottom-Up dynamic programming based on the recurrance relation.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Recursion - Breaking down problems into smaller subproblems and understanding base cases
Dynamic Programming - Recognizing overlapping subproblems and optimal substructure for memoization or tabulation
Arrays - Traversing and modifying array elements by index

1. Recursion

Intuition

From any step, you can climb 1 or 2 steps.
If you step on index i, you must pay cost[i], then choose the cheaper path ahead.
So the problem is: from each step, pick the minimum cost path to the top.

Algorithm

Define a recursive function dfs(i) = minimum cost to reach the top starting from step i.
If i is beyond the last step, cost is 0 (you reached the top).
Otherwise:
- Pay cost[i]
- Choose the minimum of:
  - Jump 1 step → dfs(i + 1)
  - Jump 2 steps → dfs(i + 2)
Since you can start from step 0 or 1, return:
- min(dfs(0), dfs(1))

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:

        def dfs(i):
            if i >= len(cost):
                return 0
            return cost[i] + min(dfs(i + 1), dfs(i + 2))

        return min(dfs(0), dfs(1))

public class Solution {
    public int minCostClimbingStairs(int[] cost) {

        return Math.min(dfs(cost, 0), dfs(cost, 1));
    }

    private int dfs(int[] cost, int i) {
        if (i >= cost.length) {
            return 0;
        }
        return cost[i] + Math.min(dfs(cost, i + 1),
                                  dfs(cost, i + 2));
    }
}

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        return min(dfs(cost, 0), dfs(cost, 1));
    }

    int dfs(vector<int>& cost, int i) {
        if (i >= cost.size()) {
            return 0;
        }
        return cost[i] + min(dfs(cost, i + 1),
                             dfs(cost, i + 2));
    }
};

class Solution {
    /**
     * @param {number[]} cost
     * @return {number}
     */
    minCostClimbingStairs(cost) {
        const dfs = (i) => {
            if (i >= cost.length) {
                return 0;
            }
            return cost[i] + Math.min(dfs(i + 1), dfs(i + 2));
        };
        return Math.min(dfs(0), dfs(1));
    }
}

public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        return Math.Min(Dfs(cost, 0), Dfs(cost, 1));
    }

    private int Dfs(int[] cost, int i) {
        if (i >= cost.Length) {
            return 0;
        }
        return cost[i] + Math.Min(Dfs(cost, i + 1),
                                  Dfs(cost, i + 2));
    }
}

func minCostClimbingStairs(cost []int) int {
    var dfs func(i int) int
    dfs = func(i int) int {
        if i >= len(cost) {
            return 0
        }
        return cost[i] + min(dfs(i+1), dfs(i+2))
    }

    return min(dfs(0), dfs(1))
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

class Solution {
    fun minCostClimbingStairs(cost: IntArray): Int {
        fun dfs(i: Int): Int {
            if (i >= cost.size) {
                return 0
            }
            return cost[i] + minOf(dfs(i + 1), dfs(i + 2))
        }

        return minOf(dfs(0), dfs(1))
    }
}

class Solution {
    func minCostClimbingStairs(_ cost: [Int]) -> Int {
        func dfs(_ i: Int) -> Int {
            if i >= cost.count {
                return 0
            }
            return cost[i] + min(dfs(i + 1), dfs(i + 2))
        }

        return min(dfs(0), dfs(1))
    }
}

impl Solution {
    pub fn min_cost_climbing_stairs(cost: Vec<i32>) -> i32 {
        fn dfs(cost: &[i32], i: usize) -> i32 {
            if i >= cost.len() {
                return 0;
            }
            cost[i] + dfs(cost, i + 1).min(dfs(cost, i + 2))
        }
        dfs(&cost, 0).min(dfs(&cost, 1))
    }
}

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$

2. Dynamic Programming (Top-Down)

Intuition

The brute force solution recomputes the same subproblems many times.
We can optimize it by remembering results once we compute them.

For each step i, the minimum cost to reach the top is:

cost[i] + minimum cost from step i+1 or i+2

By storing this result, we avoid repeated work.

Algorithm

Create a memo array where memo[i] stores the minimum cost to reach the top from step i.
Define dfs(i):
- If i is beyond the last step, return 0.
- If memo[i] is already computed, return it.
- Otherwise:
  - memo[i] = cost[i] + min(dfs(i+1), dfs(i+2))
Since you can start from step 0 or 1, return:
- min(dfs(0), dfs(1))

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        memo = [-1] * len(cost)

        def dfs(i):
            if i >= len(cost):
                return 0
            if memo[i] != -1:
                return memo[i]
            memo[i] = cost[i] + min(dfs(i + 1), dfs(i + 2))
            return memo[i]

        return min(dfs(0), dfs(1))

public class Solution {
    int[] memo;

    public int minCostClimbingStairs(int[] cost) {
        memo = new int[cost.length];
        Arrays.fill(memo, -1);
        return Math.min(dfs(cost, 0), dfs(cost, 1));
    }

    private int dfs(int[] cost, int i) {
        if (i >= cost.length) {
            return 0;
        }
        if (memo[i] != -1) {
            return memo[i];
        }
        memo[i] = cost[i] + Math.min(dfs(cost, i + 1),
                                     dfs(cost, i + 2));
        return memo[i];
    }
}

class Solution {
public:
    vector<int> memo;

    int minCostClimbingStairs(vector<int>& cost) {
        memo.resize(cost.size(), -1);
        return min(dfs(cost, 0), dfs(cost, 1));
    }

    int dfs(vector<int>& cost, int i) {
        if (i >= cost.size()) {
            return 0;
        }
        if (memo[i] != -1) {
            return memo[i];
        }
        memo[i] = cost[i] + min(dfs(cost, i + 1),
                                dfs(cost, i + 2));
        return memo[i];
    }
};

class Solution {
    /**
     * @param {number[]} cost
     * @return {number}
     */
    minCostClimbingStairs(cost) {
        const memo = new Int32Array(cost.length).fill(-1);
        const dfs = (i) => {
            if (i >= cost.length) {
                return 0;
            }
            if (memo[i] !== -1) {
                return memo[i];
            }
            memo[i] = cost[i] + Math.min(dfs(i + 1), dfs(i + 2));
            return memo[i];
        };
        return Math.min(dfs(0), dfs(1));
    }
}

public class Solution {
    int[] memo;

    public int MinCostClimbingStairs(int[] cost) {
        memo = new int[cost.Length];
        Array.Fill(memo, -1);
        return Math.Min(Dfs(cost, 0), Dfs(cost, 1));
    }

    private int Dfs(int[] cost, int i) {
        if (i >= cost.Length) {
            return 0;
        }
        if (memo[i] != -1) {
            return memo[i];
        }
        memo[i] = cost[i] + Math.Min(Dfs(cost, i + 1),
                                     Dfs(cost, i + 2));
        return memo[i];
    }
}

func minCostClimbingStairs(cost []int) int {
    memo := make([]int, len(cost))
    for i := 0; i < len(cost); i++ {
        memo[i] = -1
    }

    var dfs func(i int) int
    dfs = func(i int) int {
        if i >= len(cost) {
            return 0
        }
        if memo[i] != -1 {
            return memo[i]
        }
        memo[i] = cost[i] + min(dfs(i+1), dfs(i+2))
        return memo[i]
    }

    return min(dfs(0), dfs(1))
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

class Solution {
    fun minCostClimbingStairs(cost: IntArray): Int {
        var memo = IntArray(cost.size){-1}
        fun dfs(i: Int): Int {
            if (i >= cost.size) {
                return 0
            }
            if (memo[i] != -1) return memo[i]
            memo[i] = cost[i] + minOf(dfs(i + 1), dfs(i + 2))
            return memo[i]
        }

        return minOf(dfs(0), dfs(1))
    }
}

class Solution {
    func minCostClimbingStairs(_ cost: [Int]) -> Int {
        var memo = Array(repeating: -1, count: cost.count)

        func dfs(_ i: Int) -> Int {
            if i >= cost.count {
                return 0
            }
            if memo[i] != -1 {
                return memo[i]
            }
            memo[i] = cost[i] + min(dfs(i + 1), dfs(i + 2))
            return memo[i]
        }

        return min(dfs(0), dfs(1))
    }
}

impl Solution {
    pub fn min_cost_climbing_stairs(cost: Vec<i32>) -> i32 {
        let n = cost.len();
        let mut memo = vec![-1; n];
        fn dfs(cost: &[i32], memo: &mut Vec<i32>, i: usize) -> i32 {
            if i >= cost.len() {
                return 0;
            }
            if memo[i] != -1 {
                return memo[i];
            }
            memo[i] = cost[i] + dfs(cost, memo, i + 1).min(dfs(cost, memo, i + 2));
            memo[i]
        }
        dfs(&cost, &mut memo, 0).min(dfs(&cost, &mut memo, 1))
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Dynamic Programming (Bottom-Up)

Intuition

Instead of solving the problem recursively, we build the answer from the bottom up.

Let dp[i] represent the minimum cost to reach step i.
To reach step i, you can:

Come from step i-1 and pay cost[i-1]
Come from step i-2 and pay cost[i-2]

We choose the cheaper of the two.

Algorithm

Let n be the number of steps.
Create a DP array dp of size n+1.
Initialize:
- dp[0] = 0, dp[1] = 0 (you can start at step 0 or 1 for free).
For each step i from 2 to n:
- dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
Return dp[n] as the minimum cost to reach the top.

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]

public class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];

        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];
    }
}

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1);

        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];
    }
};

class Solution {
    /**
     * @param {number[]} cost
     * @return {number}
     */
    minCostClimbingStairs(cost) {
        const n = cost.length;
        const dp = new Array(n + 1).fill(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];
    }
}

public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        int n = cost.Length;
        int[] dp = new int[n + 1];

        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];
    }
}

class Solution {
    fun minCostClimbingStairs(cost: IntArray): Int {
        val n = cost.size
        var dp = IntArray(n + 1)

        for (i in 2..n) {
            dp[i] = minOf(dp[i - 1] + cost[i - 1],
                          dp[i - 2] + cost[i - 2])
        }

        return dp[n]
    }
}

class Solution {
    func minCostClimbingStairs(_ cost: [Int]) -> Int {
        let n = cost.count
        var dp = Array(repeating: 0, count: n + 1)

        for i in 2...n {
            dp[i] = min(dp[i - 1] + cost[i - 1],
                        dp[i - 2] + cost[i - 2])
        }

        return dp[n]
    }
}

impl Solution {
    pub fn min_cost_climbing_stairs(cost: Vec<i32>) -> i32 {
        let n = cost.len();
        let mut dp = vec![0; n + 1];

        for i in 2..=n {
            dp[i] = (dp[i - 1] + cost[i - 1]).min(dp[i - 2] + cost[i - 2]);
        }

        dp[n]
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Dynamic Programming (Space Optimized)

Intuition

At each step, you only need the minimum cost of the next one or two steps.
So instead of using a full DP array, we can reuse the input array and update it in place.

Each cost[i] is updated to represent:

the minimum cost to reach the top starting from step i.

By the end, the answer is simply the minimum cost starting from step 0 or 1.

Algorithm

Start from the third-last step and move backwards.
For each step i:
- Update cost[i] = cost[i] + min(cost[i+1], cost[i+2])
After processing all steps:
- Return min(cost[0], cost[1]) since you can start from either.

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        for i in range(len(cost) - 3, -1, -1):
            cost[i] += min(cost[i + 1], cost[i + 2])

        return min(cost[0], cost[1])

public class Solution {
    public int minCostClimbingStairs(int[] cost) {
        for (int i = cost.length - 3; i >= 0; i--) {
            cost[i] += Math.min(cost[i + 1], cost[i + 2]);
        }
        return Math.min(cost[0], cost[1]);
    }
}

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

class Solution {
    /**
     * @param {number[]} cost
     * @return {number}
     */
    minCostClimbingStairs(cost) {
        for (let i = cost.length - 3; i >= 0; i--) {
            cost[i] += Math.min(cost[i + 1], cost[i + 2]);
        }
        return Math.min(cost[0], cost[1]);
    }
}

public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        for (int i = cost.Length - 3; i >= 0; i--) {
            cost[i] += Math.Min(cost[i + 1], cost[i + 2]);
        }
        return Math.Min(cost[0], cost[1]);
    }
}

class Solution {
    fun minCostClimbingStairs(cost: IntArray): Int {
        val n = cost.size
        for (i in n - 3 downTo 0) {
            cost[i] += minOf(cost[i + 1], cost[i + 2])
        }
        return minOf(cost[0], cost[1])
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Misunderstanding the Goal Position

The top of the staircase is at index n (one step past the last stair), not at index n-1. You need to reach beyond the last step, so your DP array or recursion must account for landing on position n, not just visiting the last cost element.

Forgetting You Can Start from Step 0 or Step 1

The problem allows starting from either step 0 or step 1 without paying any cost initially. A common mistake is assuming you must start from step 0 only, which can lead to suboptimal solutions when starting from step 1 would be cheaper.

Incorrect Base Cases in DP

When using bottom-up DP, the base cases should be dp[0] = 0 and dp[1] = 0 because you can stand on step 0 or step 1 for free before paying to move forward. Setting these incorrectly, such as dp[0] = cost[0], misinterprets when you pay the cost.