Python - Min Cost Climbing Stairs in Python

The Min Cost Climbing Stairs problem is a classic Dynamic Programming problem that appears frequently in coding interviews. This problem requires finding the minimum cost to reach the top of a staircase, given an array where each element represents the cost of stepping on that stair.

Problem Statement

You are given an integer array cost where cost[i] represents the cost of the i-th step. Once you pay the cost, you can climb either one or two steps. You can either start from the 0-th or 1-st step. The goal is to reach the top with the minimum cost.

Example

Input: cost = [10, 15, 20]

Output: 15

Explanation:

Start from index 1 (cost = 15) → jump to the top.

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

Output: 6

Explanation:

Start at index 0 (cost = 1) → step 2 (cost = 1) → step 3 (cost = 1) → step 4 (cost = 1) → step 6 (cost = 1) → step 7 (cost = 1) → step 9 (cost = 1).

Total cost = 6.

Approach

We solve this using Dynamic Programming:

Bottom-up DP (Tabulation)

Define dp[i] as the minimum cost to reach the i-th step.

The recurrence relation is:

dp[i]=min(dp[i−1],dp[i−2])+cost[i]

Start from the 0-th or 1-st step and compute the cost.

Optimized Space Complexity (Using Two Variables)

Instead of storing an entire DP array, maintain only two variables for the previous steps.

Python Solution

Method 1: Using a DP Array

def minCostClimbingStairs(cost):

    n = len(cost)

    dp = [0] * (n + 1)  # One extra step for reaching the top

    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]

# Example

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]

print(minCostClimbingStairs(cost))  # Output: 6

Method 2: Optimized Space Complexity (O(1))

def minCostClimbingStairs(cost):

    prev1, prev2 = 0, 0  # Represents dp[i-1] and dp[i-2]

    for i in range(2, len(cost) + 1):

        curr = min(prev1 + cost[i - 1], prev2 + cost[i - 2])

        prev2, prev1 = prev1, curr  # Shift variables

    return prev1

# Example

cost = [10, 15, 20]

print(minCostClimbingStairs(cost))  # Output: 15