Climbing Stairs

Dynamic programming · Remember repeated smaller answers · Easy · about 18 min

Why it matters

Dynamic programming starts with one question: am I solving the same smaller state repeatedly?

How it connects

Fibonacci repeated subproblems; now you keep those answers instead of calculating them again.

Try first

How many ways can reach step n from the two steps immediately before it?

Interview cue

This is Fibonacci with a meaning: each state is the number of ways to reach a step.