70. Climbing Stairs

https://leetcode.com/problems/climbing-stairs

Python

Bottom-Up DP

class Solution:
    def __init__(self):
        self.memory = dict()

    def climbStairs(self, n: int) -> int:
        if n in self.memory:
            return self.memory[n]

        if n <= 3:
            return n

        self.memory[n] = self.climbStairs(n-1) + self.climbStairs(n-2)

        return self.memory[n]

Top-Down DP

class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 2:
            return 1

        dp = [0] * n
        dp[0], dp[1] = 1, 2

        for i in range(2, n):
            dp[i] = dp[i-1] + dp[i-2]

        return dp[-1]