Climbing Stairs

Climbing Stairs is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 1D Array (Fibonacci Style) subpattern.

Problem statement

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps

Example 2:

Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step

Constraints:

- 1 <= n <= 45

Topics and companies

Topics: Math, Dynamic Programming, Memoization.

Reported in interviews at Adobe, Amazon, Apple, Bloomberg, Expedia, Facebook, Goldman Sachs, Google, Intuit, Microsoft, Nvidia.

How to practise Climbing Stairs on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(logn) time and O(1) space.

Open Climbing Stairs in the code editor, or read the Climbing Stairs editorial for a worked solution with its approach and complexity analysis.

Where Climbing Stairs sits in the DSA pattern sheet

• Dynamic Programming (DP) Patterns pattern guide
• 1D Array (Fibonacci Style) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Climbing Stairs

Other problems that use the same 1D Array (Fibonacci Style) and Dynamic Programming (DP) Patterns techniques:

• Decode Ways — Medium, same subpattern
• Delete and Earn — Medium, same subpattern
• Fibonacci Number — Easy, same subpattern
• House Robber — Medium, same subpattern
• House Robber II — Medium, same subpattern
• Min Cost Climbing Stairs — Easy, same subpattern