FilesExpand file tree

main

/

climbing_stairs_top_down.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

13 lines (12 loc) · 509 Bytes

main

/

climbing_stairs_top_down.py

Copy path

Top

File metadata and controls

• Code
• Blame

13 lines (12 loc) · 509 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

memo = {}

def climbing_stairs_top_down(n: int) -> int:

# Base cases: With a 1-step staircase, there's only one way to

# climb it. With a 2-step staircase, there are two ways to climb it.

if n <= 2:

return n

if n in memo:

return memo[n]

# The number of ways to climb to the n-th step is equal to the sum

# of the number of ways to climb to step n - 1 and to n - 2.

memo[n] = (climbing_stairs_top_down(n - 1) + climbing_stairs_top_down(n - 2))

return memo[n]