forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathclimbing_stairs.py
More file actions
60 lines (46 loc) · 1.3 KB
/
climbing_stairs.py
File metadata and controls
60 lines (46 loc) · 1.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
"""
Climbing Stairs
Count the number of distinct ways to climb a staircase of n steps,
where each move is either 1 or 2 steps.
Reference: https://leetcode.com/problems/climbing-stairs/
Complexity:
climb_stairs:
Time: O(n)
Space: O(n)
climb_stairs_optimized:
Time: O(n)
Space: O(1)
"""
from __future__ import annotations
def climb_stairs(steps: int) -> int:
"""Count distinct ways to climb n steps using a list-based DP approach.
Args:
steps: Number of steps in the staircase (positive integer).
Returns:
Number of distinct ways to reach the top.
Examples:
>>> climb_stairs(2)
2
>>> climb_stairs(10)
89
"""
arr = [1, 1]
for _ in range(1, steps):
arr.append(arr[-1] + arr[-2])
return arr[-1]
def climb_stairs_optimized(steps: int) -> int:
"""Count distinct ways to climb n steps using constant space.
Args:
steps: Number of steps in the staircase (positive integer).
Returns:
Number of distinct ways to reach the top.
Examples:
>>> climb_stairs_optimized(2)
2
>>> climb_stairs_optimized(10)
89
"""
a_steps = b_steps = 1
for _ in range(steps):
a_steps, b_steps = b_steps, a_steps + b_steps
return a_steps