took the time to learn the framework for dp. below are some notes from the leetcode explore for DP.

characteristics of dp:

• break down into overlapping subproblems
• an optimal solution can be formed

what dp is not:

• greedy problems have optimal substructure, but not overlapping subproblems
• divide and conquer breaks a problem into subprobelms, but they are not overlapping

why it helps?

• it improves time complexity compared to brute force
• ex: fib(n) has exponential time complexity for brute force, while linear with DP, as it reuses results of subproblems raather than recalculating results for previously seen subproblems

top-down vs bottom up

• top down (tabulation)

  • iteration and starts with a basecase
  • order matters
  • usually faster, no recursion overhead

    # fibonacci
    F = [0] * (n+1)
    F[0] = 1
    F[1] = 1
    for i in range(2, n):
        F[i] = F[i-1] + F[i-2]

• bottom-up (memoization)

  • recursion and made efficient with memoization

  • easier to write, order does not matter

  • slower

    memo = {}
    def f(i):
        if i < 2:
            return i
    
        if i not in memo:
            memo[i] = f(i-1) + f(i-2)
    
        return memo[i]

when to use it?

1. problem asks for optimum value (max/min) of something
   • min cost of doing ... , how many ways are there to ... , longest possible ...
   • not enough by itself, could be greedy
2. future "decisions" depends on earlier decisions
   • ex: house robber
     • nums = [2,7,9,3,1]
     • greedy solution is to rob 7, but you miss out on 9 (your early decision affects future decisions)
   • ex: longest increasing subsequence
     • nums = [1,2,6,3,5]
     • important decision is choosing 6 or not, this affects the future (whether you can take 3 and 5)

framework

1. a function that computes answer to problem for every given state
   • ex: climbing stairs, we have dp(i) which returns number of ways to climb ith step.
2. a recurrence relation to transition between states
   • to climb the 10th stair, we need to climb from the 8th or 9th
   • so # ways to climb 10th stair is # ways to climb 8th + # ways to climb 9th stair
     • dp(i) = dp(i-1) + dp(i-2)
   • finding this is the most difficult part
3. base cases (to prevent it going infinitely)
   • ask yourself: what state can you find answer without using DP?
   • there is one way to climb first stair, and two ways to climb two stairs,
   • base case = dp(1) = 1 and dp(2) = 2

recurrence -> O(2^n)

def climbStairs(self, n: int) -> int:
    def dp(i):
        """A function that returns the answer to the problem for a given state."""
        # Base cases: when i is  3 there are i ways to reach the ith stair.
        if i <= 2:
            return i

        # If i is not a base case, then use the recurrence relation.
        return dp(i - 1) + dp(i - 2)

    return dp(n)

add memoization -> O(n)

def climbStairs(self, n: int) -> int:
    def dp(i):
        if i <= 2:
            return i
        if i not in memo:
            # Instead of just returning dp(i - 1) + dp(i - 2), calculate it once and then
            # store the result inside a hashmap to refer to in the future.
            memo[i] = dp(i - 1) + dp(i - 2)

        return memo[i]

    memo = {}
    return dp(n)

bottom up approach

def climbStairs(self, n: int) -> int:
    if n == 1:
        return 1

    # An array that represents the answer to the problem for a given state
    dp = [0] * (n + 1)

    # base case
    dp[1] = 1
    dp[2] = 2

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

    return dp[n]