Climbing Stairs

Easy

dynamic-programming

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?

This is the classic introduction to Dynamic Programming. The key insight is that the number of ways to reach step n equals the sum of ways to reach step n-1 (then take 1 step) plus the ways to reach step n-2 (then take 2 steps).

Recurrence Relation: dp[i] = dp[i-1] + dp[i-2]

This follows the Fibonacci sequence pattern, making it an excellent first DP problem.

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: (1) 1+1+1, (2) 1+2, (3) 2+1

Example 3

Input: n = 4

Output: 5

Explanation: Five ways: (1) 1+1+1+1, (2) 1+1+2, (3) 1+2+1, (4) 2+1+1, (5) 2+2

Constraints

•1 <= n <= 45

Show Hints (4)

Hint 1: Think about the last step. How did you get there?

Hint 2: You either took 1 step from n-1, or 2 steps from n-2.

Hint 3: The number of ways to reach step n is the sum of ways to reach n-1 and n-2.

Hint 4: What are the base cases? How many ways to reach step 1? Step 2?

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?