Min Cost Climbing Stairs

Examples

Input: cost = [10, 15, 20]
Output: 15

Start on step 1 (free), pay 15 to jump 2 steps straight to the top.

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

Start on step 0, then hop over every expensive step, paying 1 six times.

Constraints

• 2 <= cost.length <= 1000

• 0 <= cost[i] <= 999

Approach

Picture standing on some step i. From there you must pay cost[i] no matter which way you jump, and then you land either on step i+1 or step i+2. So the cheapest way to finish from step i is cost[i] plus whichever of "finish from i+1" or "finish from i+2" is cheaper. That's a recursive relationship, just like Climbing Stairs, but minimizing instead of counting.

Since "finish from the top" and "finish from one past the top" both cost 0 (you're already there), you can build the answer up from the end of the array backward — or equivalently, build up from the front by asking "what's the cheapest way to arrive at step i", and finish by taking the smaller of arriving at the last two steps (since either one is one hop from the top).

Solutions

Brute Force — Plain Recursion

Recurse on 'cheapest cost to finish starting from step i': pay cost[i], then take the cheaper of jumping 1 or 2 steps. Correct, but re-explores the same steps over and over.

function minCostClimbingStairs(cost) {
  const n = cost.length;

  function finishFrom(i) {
    if (i >= n) return 0;
    return cost[i] + Math.min(finishFrom(i + 1), finishFrom(i + 2));
  }

  return Math.min(finishFrom(0), finishFrom(1));
}

Time: O(2^n) · Space: O(n) — recursion depth

Optimal — Bottom-Up with Two Variables

Walk forward and track the cheapest cost to arrive at each step, using only the previous two results. The top is one hop past the last step, so the answer is the smaller of the costs to arrive at the last two steps.

function minCostClimbingStairs(cost) {
  const n = cost.length;

  // Cheapest cost to arrive at step 0 or step 1 is 0 (both are free starts).
  let prev2 = 0;
  let prev1 = 0;

  for (let i = 2; i <= n; i++) {
    const current = Math.min(
      prev1 + cost[i - 1],
      prev2 + cost[i - 2]
    );
    prev2 = prev1;
    prev1 = current;
  }

  return prev1;
}

Time: O(n) · Space: O(1)