Medium

Climbing Stairs - Count Distinct Ways

Time limit: 2 s
Memory limit: 128 MB
Estimated: 15 min

DP Foundations

Description

You are climbing a staircase that has n steps. Each time you can climb either 1 step or 2 steps. Write a recursive function that returns how many distinct ways you can climb to the top.

Recursively:

climbStairs(1) = 1
climbStairs(2) = 2
climbStairs(n) = climbStairs(n - 1) + climbStairs(n - 2) for n > 2, because the last move to reach step n is either a single step from step n - 1 or a double step from step n - 2.

Example: n = 5 returns 8.

Plain recursion without caching is exponential and will time out on the larger inputs. Use memoized recursion so each climbStairs(k) is computed only once.

Constraints

1 <= n <= 50

Sample cases

Sample 1
Input
```
n = 1
```
Expected output
```
1
```
Sample 2
Input
```
n = 2
```
Expected output
```
2
```
Sample 3

Skills and languages

Concepts

Memoization

Languages

Python 3

Solve this problem

Create a free account to write, run and submit your solution.

Write Python or Java in the browser, with your draft saved as you type
Run your code on the examples as often as you like
Submit to a sandboxed judge and see exactly which case failed
Ask the AI mentor for a hint without being handed the answer

Create free account

Sample 1

Input

Expected output

Sample 2

Input

Expected output

Sample 3

Concepts

Languages

Solve this problem

Input

Expected output