#746 - Min Cost Climbing Stairs

EasyDP - 1D

Given an integer array cost where cost[i] is the cost of step i, you can start from step 0 or 1. Each time, climb 1 or 2 steps. Return the minimum cost to reach the top (one step past the last index).

Input	Output
cost = [10,15,20]	15
cost = [1,100,1,1,1,100,1,1,100,1]	6

Solution Space

Try it

/**
 * Returns the minimum cost to climb to the top of the staircase.
 *
 * @param cost cost[i] = cost to step on stair i
 * @returns Minimum cost to reach past the last step
 */
export function minCostClimbingStairs(cost: number[]): number {
  const n = cost.length;
  let prev2 = 0; // cost to reach 2 steps behind
  let prev1 = 0; // cost to reach 1 step behind

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

  return prev1;
}

Approach: bottom-up DP with O(1) space – `dp[i]` = min cost to reach step `i`. Since we only look back 2 steps, two variables suffice.

Time: O(n) – single pass.

Space: O(1) – two rolling variables.

#198 House Robber

#1137 N-th Tribonacci Number