climbing stairs Algorithm
The climbing stairs algorithm is a simple, yet effective, dynamic programming problem that is often used to illustrate the concept of recursion and memoization. It is a classic problem that involves finding the number of distinct ways one can climb a staircase, given that they can take either one or two steps at a time. The problem is typically framed as follows: given a staircase with 'n' steps, how many unique ways can a person climb it, if they are allowed to take either one or two steps at a time?
To solve this problem, the climbing stairs algorithm utilizes dynamic programming techniques to break the problem down into smaller subproblems, and then combine their solutions. The basis of the algorithm is the understanding that the number of ways to reach step 'n' depends on the number of ways to reach steps 'n-1' and 'n-2', since a person can take a single step from 'n-1' or a double step from 'n-2' to reach 'n'. Therefore, the problem can be expressed as a recurrence relation, with the number of ways to climb 'n' steps being equal to the sum of the ways to climb 'n-1' steps and 'n-2' steps. By using memoization to store intermediate results, the algorithm can efficiently solve the problem with a time complexity of O(n) and a space complexity of O(n).
#!/usr/bin/env python3
def climb_stairs(n: int) -> int:
"""
LeetCdoe No.70: Climbing Stairs
Distinct ways to climb a n step staircase where
each time you can either climb 1 or 2 steps.
Args:
n: number of steps of staircase
Returns:
Distinct ways to climb a n step staircase
Raises:
AssertionError: n not positive integer
>>> climb_stairs(3)
3
>>> climb_stairs(1)
1
>>> climb_stairs(-7) # doctest: +ELLIPSIS
Traceback (most recent call last):
...
AssertionError: n needs to be positive integer, your input -7
"""
fmt = "n needs to be positive integer, your input {}"
assert isinstance(n, int) and n > 0, fmt.format(n)
if n == 1:
return 1
dp = [0] * (n + 1)
dp[0], dp[1] = (1, 1)
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
if __name__ == "__main__":
import doctest
doctest.testmod()
