climb_stairs.py

class Solution:
    def climbStairs(self, n: int) -> int:
        """
        Tabulation:
        - Depends on the base solution that is being set
        - Solved in the direction of solving the base cases to the main problem

        Intuition:
        - To reach step i, look back at how to go there in one move.
	    - Either came from one step before or two steps before.
        - Summing those possibilities covers all ways to get to i.
        """

        if n == 0 or n == 1:
            return 1

        dp = [0] * (n + 1)
        dp[0] = 1 # how many ways to reach step 0? 1 way: do nothing
        dp[1] = 1 # how many ways to reach step 1? 1 way: 1 step

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

        return dp[n]

        # Time Complexity: O(n)
        # Space Complexity: O(n)