Climbing Stairs

Asked byAmazonExpediaMicrosoftUberGoogleAdobe

Problem

You are climbing a staircase with n steps. Each move you can climb either 1 or 2 steps. Return the number of distinct ways you can climb to the top.

Examples

Example 1

Input:n = 2

Output:2

1+1 or 2.

Example 2

Input:n = 3

Output:3

1+1+1, 1+2, or 2+1.

Constraints

1 <= n <= 45

Try it now — no sign-up needed. Write your solution in Python or JavaScript, run it against test cases, and submit for a verdict, right in your browser.

Open the editor →

How to approach it: the 1-D Dynamic Programming pattern

Break a problem into overlapping subproblems along a single dimension — like "the answer up to index i" — solve each one once, and reuse the result instead of recomputing it.

Look for this pattern when

A greedy or purely recursive approach recomputes the same subproblem repeatedly.
The problem asks for a count, a minimum/maximum, or a yes/no reachability over a sequence, where the answer at position `i` depends on answers at earlier positions.

Read the full 1-D Dynamic Programming guide →

Video walkthroughs

Original problem on LeetCode ↗