746. Min Cost Climbing Stairs

Using python and go

Problem Statement

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.

Examples

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

Intuition

This problem is a great fit for solving with recursion. Let's try to tackle it using the recursive framework we explored in The Recursive Journey blog:

Identify actual problem: The actual problem here is to find the minimum cost to reach top floor.

$$minCostClimbingStairs(n)$$

Identify sub-problem: If we know the cost reach (n-1)th step or (n-2)th, we can easily calculate the cost to reach nth floor.
Trust that the base function works: We have confidence in the function that computes the cost to reach n steps. It is designed to work effectively for all sub-problems and deliver the accurate solution.
Link actual and sub-problem: Since we have found minCostClimbingStairs(n-1) and minCostClimbingStairs(n-2) stairs we can just do:

minCostClimbingStairs(n) = cost[n]+min(minCostClimbingStairs(n-1), minCostClimbingStairs(n-2))

Identify base case: Since we're moving from the 0th index of the cost array to the nth index (the length of the cost array), we cannot exceed the nth index. Therefore:
```
  if stair>=len(cost):
      return 0
```
This will make sure recursive function does not go beyond the bounds of cost array.

If you observe, we can solve this issue by moving through the cost array in two directions:

from the 0th to the nth index

from the nth to the 0th index.

The explanation above covers moving through the cost array from the 0th index to the nth index.

The concept for moving through the cost array from the nth index to the 0th index remains the same. Only the code we write and the base condition change slightly. Below, we will see code solutions for both approaches.

Solution

Code in python

from the 0th to the nth index:

# from the 0th to the nth index
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        return min(self.climb(0,cost),self.climb(1,cost))
    def climb(self,stair:int,cost:List[int])->int:
        # base condition
        if stair>=len(cost):
            return 0
        return cost[stair]+min(self.climb(stair+1,cost),self.climb(stair+2,cost))

from the nth to the 0th index.

#  from the nth to the 0th index
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n=len(cost)
        return min(self.climb(n-1,cost),self.climb(n-2,cost))
    def climb(self,stair,cost):
        # base condition
        if stair<=1:
            return cost[stair]
        return cost[stair]+min(self.climb(stair-1,cost),self.climb(stair-2,cost)

Code in go

from the 0th to the nth index:

func minCostClimbingStairs(cost []int) int {
    return min(climb(0,cost),climb(1,cost))
}
func climb(stair int,cost []int) int{
    // base condition
    if stair>=len(cost){
        return 0
    }
    return cost[stair]+min(climb(stair+1,cost),climb(stair+2,cost))
}
// function to calculate minimum of two numbers
func min(a, b int) int{
    if a < b{
        return a
    }
    return b
}

from the nth to the 0th index.

func minCostClimbingStairs(cost []int) int {
    n:=len(cost)
    return min(climb(n-1,cost),climb(n-2,cost))
}
func climb(stair int,cost []int) int{
    // base condition
    if stair<=1{
        return cost[stair]
    }
    return cost[stair]+min(climb(stair-1,cost),climb(stair-2,cost))
}
// function to calculate minimum of two numbers
func min(a, b int) int{
    if a < b{
        return a
    }
    return b
}

Note: these solutions will give TimeLimitExceeded error on leetcode. Don't worry we will improve these in the Dynamic Programming series.

Time and space complexity

Time Complexity:

$$𝑂(2^𝑛)$$

This occurs because with each recursive function call, two additional recursive calls are made.

Space complexity:

If you observe the code, no data structure is being used. However, due to recursion, the compiler allocates space in the heap for each recursive call on the call stack. Therefore, the space complexity is:

$$O(n)$$

Conclusion

As you can see 746. Min Cost Climbing Stairs can be solved using recursion. There are two ways to solve this problem using recursion:

from the 0th to the nth index
from the nth to the 0th index

Although these are decent solutions, they're just basic recursion without any fancy optimizations. But hey, no worries, we'll dive into those optimizations in the Dynamic Programming series.

I hope you got something useful from this blog post. If you've made it this far, please give it a like and drop your thoughts in the comments. Feel free to share any ideas for making future blog posts better.