loading

Min Cost Climbing Stairs — Step-by-Step Visualization

easyLeetCode #746ArrayDynamic Programming

You are given an integer array `cost` where `cost[i]` is the cost of `i-th` 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.

Algorithm Pattern

1D Dynamic Programming

Key Idea

To reach step `i`, we must have come from either step `i-1` or step `i-2`. Thus, the minimum cost to reach step `i` is `cost[i] + min(minCost[i-1], minCost[i-2])`. Since the 'top of the floor' is one step beyond the last element of the `cost` array, we need to find the minimum of the last two calculated costs.

Step-by-Step Approach

  1. Initialize `dp = [0] * (len(cost) + 1)`.
  2. For `i` from 2 to `len(cost)`:
  3. `dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])`.
  4. Return `dp[len(cost)]`.

Common Gotchas

  • The 'top' is reached when you step *past* the last index.
  • Base cases are `dp[0] = 0` and `dp[1] = 0` because you can start at either step 0 or 1 for free.

Related Problems

← All problems