Dynamic Programming

Intro

Dynamic Programming is a technique aimed at taking advantage of overlapping subproblems.

It involves breaking down a problem into its subproblems, solving each subproblem only once, and storing its result to avoid redundant calculations

Here is a good refresher video to dynamic programming.

First easy steps to Dynamic Programming:

1. Define Subproblems
2. Guess (part of sol.)
3. Recurrence (time/sub)
4. Recurse and memoize (check recurrence is acyclic) or Build it Botton-up (need a topological order) We get the total running time = # subproblems * time/subproblem
5. Solve Original Problem

Dynamic Programming I: Fibonacci Numbers

Calculate the nth Fibonacci numbers: where F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2) for n ≤ 2

Recursive Approach (Inefficient)

    def fibRecursive(self, n: int):

        # base case: fib(0) = 0
        if n == 0:
            return 0

        # base case: fib(1) = 1
        if n == 1:
            return 1

        # recursively calculate fib 
        return fibRecursive(n - 1) + fibRecursive(n - 2)

ASCII Diagram for Recursive Approach
                   F(5)
                /        \
            F(4)         F(3)
            /    \       /   \
        F(3)    F(2)   F(2) F(1)
        /   \   /   \     
    F(2)  F(1) F(1) F(0)
    /   \
    F(1) F(0)

Redundant Calculations: F(3) is calculated twice. F(2) is calculated three times. etc...

Exponential Growth: The time complexity is O(2ⁿ).

Dynamic Programming Approach (Efficient)

    def fibDp(self, n: int):

        # Table to store results and build up solution
        # space complexity: 
        dp = [0] * (n + 1) 
        
        # Base case: Fib(0) = 0 and Fib(1) = 1
        dp[0], dp[1] = 0, 1

        # time complexity: iterate over list of n length O(n)
        for i in range(2, n + 1):

            # Transition relation
            dp[i] = dp[i - 1] + dp[i - 2]  

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return dp[n]

Dynamic Programming Table Evolution

    Step 0: Initialize base cases
    Index:  0   1   2   3   4   5
    Value:  0   1   -   -   -   -

    Step 1: Compute F(2) = F(1) + F(0)
    Index:  0   1   2   3   4   5
    Value:  0   1   1   -   -   -

    Step 2: Compute F(3) = F(2) + F(1)
    Index:  0   1   2   3   4   5
    Value:  0   1   1   2   -   -

    Step 3: Compute F(4) = F(3) + F(2)
    Index:  0   1   2   3   4   5
    Value:  0   1   1   2   3   -

    Step 4: Compute F(5) = F(4) + F(3)
    Index:  0   1   2   3   4   5
    Value:  0   1   1   2   3   5

Avoided Redundant Calculations: F(3) is calculated once. F(2) is calculated once.

Time complexity:

Dynamic Programming I: Shortest Path

Dynamic Programming II: Text Justification

Dynamic Programming II: Blackjack