unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 70: Climbing Stairs

link

Dynamic Programming

Subproblem

Let S(i) be the number of ways to climb i stairs. Then:

S(i) = \begin{cases} 1, & \text{if } i = 1 \\ 2, & \text{if } i = 2 \\ S(i-1) + S(i-2) & \text{otherwise} \end{cases}

Time: \mathcal{O}(n), space: \mathcal{O}(1).

class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 3:
            return n
        prev, curr = 1, 2
        for _ in range(n-2):
            prev, curr = curr, prev+curr
        return curr

tanvirdotzaman

Leave a comment