746. Min Cost Climbing Stairs

At a Glance

• Topic: dp-1d
• Pattern: Dynamic Programming (linear minimum cost)
• Difficulty: Easy
• Companies: Amazon, Google, Adobe, Uber, Bloomberg
• Frequency: High
• LeetCode: 746

Problem (one-liner)

Each stair index has a non-negative cost[index]. Pay that cost to step onto it; start at index 0 or 1. Reach past the last index with minimum total cost. Input: cost array. Output: minimum sum.

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

• “Minimum cost” + “from step i you can go to i+1 or i+2”
• Start position choice (first or second stair)
• Top is beyond last index (pay once then exit)

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — enumerate all paths — exponential time.
• Better — top-down memo from each index — O(n) time / O(n) space.
• Optimal — bottom-up min of two predecessors — O(n) time / O(1) space. <- pick this in interview.

Optimal Solution

Go

package main

func minCostClimbingStairsTable(cost []int) int {
	length := len(cost)
	dp := make([]int, length+1)
	dp[0], dp[1] = 0, 0
	for index := 2; index <= length; index++ {
		payCurrent := dp[index-1] + cost[index-1]
		payPrevious := dp[index-2] + cost[index-2]
		if payCurrent < payPrevious {
			dp[index] = payCurrent
		} else {
			dp[index] = payPrevious
		}
	}
	return dp[length]
}

func minCostClimbingStairs(cost []int) int {
	length := len(cost)
	prevPrev := 0
	prev := 0
	for index := 2; index <= length; index++ {
		payCurrent := prev + cost[index-1]
		payPrevious := prevPrev + cost[index-2]
		next := payCurrent
		if payPrevious < payCurrent {
			next = payPrevious
		}
		prevPrev = prev
		prev = next
	}
	return prev
}

JavaScript

function minCostClimbingStairsTable(cost) {
	const length = cost.length;
	const dp = new Array(length + 1).fill(0);
	for (let index = 2; index <= length; index++) {
		dp[index] = Math.min(
			dp[index - 1] + cost[index - 1],
			dp[index - 2] + cost[index - 2]
		);
	}
	return dp[length];
}

function minCostClimbingStairs(cost) {
	const length = cost.length;
	let prevPrev = 0;
	let prev = 0;
	for (let index = 2; index <= length; index++) {
		const next = Math.min(
			prev + cost[index - 1],
			prevPrev + cost[index - 2]
		);
		prevPrev = prev;
		prev = next;
	}
	return prev;
}

Walkthrough

Input: cost = [10, 15, 20]

Reach past index 2 with cost 10.

Invariant: dp[index] is min cost to stand on step index (or 0 for virtual start); transition always adds cost of the stair you step onto.

Edge Cases

• Length 2: answer is min(cost[0], cost[1])
• All zeros → answer 0
• Large costs still fit in int for typical constraints

Pitfalls

• Adding cost of stair you leave instead of stair you land on
• Confusing “top” as last index instead of one past last
• Allocating dp of length n only — need n+1 for destination past last stair

Similar Problems

• 70. Climbing Stairs — counting paths without costs.
• 198. House Robber — adjacent constraint with max sum.

Variants

• Variable jump lengths → longer rolling window or full table.
• Must land exactly on last stair (no “past top”) → shift indices in recurrence.

Mind-Map Tags

#dp-1d #linear-dp #min-cost-path #rolling-state #easy