5 Best Ways to Find Minimum Cost to Climb to the Top of Stairs in Python

Rate this post

πŸ’‘ Problem Formulation: Given a staircase where each step has an associated cost, our goal is to find the minimum cost required to reach the top of the stairs. The input is a list where the ith element represents the cost of the ith step, and we can either start from step 0 or step 1. The output is the minimum cost to reach a step that is beyond the topmost step (either the last or second-to-last step).

Method 1: Dynamic Programming

This method uses dynamic programming to iteratively calculate the minimum cost of reaching each step based on the previously calculated steps. The function minCostClimbingStairs(cost) returns the minimum cost to reach the top of a staircase, where cost is a list of integers representing the cost of each step.

Here’s an example:

def minCostClimbingStairs(cost):
      dp = [0] * (len(cost) + 1)
      for i in range(2, len(cost) + 1):
          dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
      return dp[-1]

  # Example usage:
  print(minCostClimbingStairs([10, 15, 20]))

Output: 15

This code initializes a dynamic programming array dp to store the minimum cost to reach each step, starting with 0 for the first two steps. It then iterates through the steps, calculating the cost based on the previous two steps, and returns the last element of dp.

Method 2: Recursive Approach with Memoization

Recursion with memoization is a technique to avoid redundant calculations by storing the results of expensive function calls. The function minCost() recursively finds the minimum cost to the top of the stairs, caching the results to improve efficiency.

Here’s an example:

def minCostClimbingStairs(cost):
      memo = {}
      
      def minCost(i):
          if i <= 1:
              return 0
          if i not in memo:
              memo[i] = min(minCost(i - 1) + cost[i - 1], minCost(i - 2) + cost[i - 2])
          return memo[i]
      
      return minCost(len(cost))

  # Example usage:
  print(minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))

Output: 6

This code snippet defines a recursive function minCost(), which calculates the cost of reaching the ith step. The memoization dictionary memo is used to cache the results, reducing the overall number of calculations needed.

Method 3: Optimized Dynamic Programming

By optimizing space complexity, this method keeps track of only the last two steps’ costs instead of using an entire list. The minCostClimbingStairs() function computes the minimum cost with reduced space requirements.

Here’s an example:

def minCostClimbingStairs(cost):
      a, b = 0, 0
      for i in range(2, len(cost) + 1):
          a, b = b, min(b + cost[i - 1], a + cost[i - 2])
      return b

  # Example usage:
  print(minCostClimbingStairs([10, 15, 3, 7]))

Output: 10

This approach keeps two variables, a and b, to store the minimum cost to reach the last two steps. It updates these variables iteratively, ensuring the space complexity is O(1), as it doesn’t rely on a list to store the cost of all steps.

Method 4: Greedy Approach

In certain cost configurations, a greedy approach can reach a solution by always choosing the next step based on the current cheapest option. The function minCostClimbingStairs() uses this philosophy to calculate the minimum cost, though it may not work for all cases.

Here’s an example:

def minCostClimbingStairs(cost):
      step1, step2 = 0, min(cost[0], cost[1])
      for i in range(2, len(cost)):
          next_step = cost[i] + min(step1, step2)
          step1, step2 = step2, next_step
      return min(step1, step2)

  # Example usage:
  print(minCostClimbingStairs([0, 2, 2, 1]))

Output: 2

This example uses a bottom-up approach, accumulating the cost in two variables step1 and step2. For each step, it updates these variables taking the minimum of the two options, simulating a greedy choice.

Bonus One-Liner Method 5: Pythonic Reduction

The one-liner uses Python’s reduce function to apply a similar approach to the optimized dynamic programming example but in a single, elegant line of code. However, this approach might not be readily understandable to beginners.

Here’s an example:

from functools import reduce

  def minCostClimbingStairs(cost):
      return reduce(lambda acc, cur: (acc[1], min(acc) + cur), cost, (0, 0))[1]

  # Example usage:
  print(minCostClimbingStairs([10, 15, 20]))

Output: 15

This one-liner uses reduce() to iterate over the list, carrying an accumulator acc that holds the last two minimum costs. The final minimum cost is extracted from the accumulator.

Summary/Discussion

  • Method 1: Dynamic Programming. Time-efficient. Requires extra space proportional to the number of stairs.
  • Method 2: Recursive Approach with Memoization. Intuitive. Potential stack overflow for very long staircases due to deep recursion.
  • Method 3: Optimized Dynamic Programming. Very space-efficient. Can be less readable to those unfamiliar with space optimization techniques.
  • Method 4: Greedy Approach. Simple and intuitive. Not guaranteed to work for all cost configurations, potentially leading to incorrect results.
  • Bonus Method 5: Pythonic Reduction. Elegant and compact. May sacrifice readability for conciseness, especially for those not comfortable with functional programming paradigms.