Dynamic Programming Basics

This lesson on Dynamic Programming Basics is hands-on and example-driven. You will optimize exponential-time recursive algorithms down to linear time by identifying overlapping subproblems. You will master both top-down memoization to cache subproblem results and bottom-up tabulation to iteratively construct state arrays from base cases.

What You'll Be Able To Do

• Identify overlapping subproblems in naive recursive algorithms that cause exponential time complexity.
• Implement top-down dynamic programming by attaching a memoization cache to recursive functions.
• Formulate bottom-up dynamic programming algorithms using iterative array tabulation starting from base cases.
• Evaluate and contrast time and space complexity shifts from exponential O(2^N) down to linear O(N).

Detailed Concept Walkthrough

1. Foundations of Dynamic Programming

Dynamic Programming (DP) optimizes recursive problems by caching intermediate results to eliminate redundant duplicate calculations across overlapping subproblems.

• Mechanism: When a problem exhibits overlapping subproblems, a naive recursive call tree computes identical states multiple times across different branches. DP resolves this inefficiency by evaluating each distinct subproblem exactly once and storing its output in a table.
• Under the Hood: Naive recursion creates a branching call stack with a depth proportional to N, generating an exponential O(2^N) state space. Storing results restricts the state space to distinct subproblem inputs, shrinking the total operational count to linear O(N).
• Best Practice: Always formulate and verify the base cases and mathematical recurrence relation (such as f(N) = f(N-1) + f(N-2)) before introducing any caching structures.

# Naive recursive implementation: O(2^N) time complexity
def fib_naive(n):
    # Base cases: return n directly for first states
    if n <= 1:
        return n
    # Redundant recursive branching causes exponential call tree
    return fib_naive(n - 1) + fib_naive(n - 2)

Key Takeaway: Dynamic programming avoids re-evaluating identical subproblems by persisting intermediate computation results.

2. Top-Down Dynamic Programming via Memoization

Memoization preserves the natural top-down recursive call structure while intercepting calls with a lookup cache to return precomputed answers instantly.

• Execution Flow: The function receives a state parameter N and immediately inspects a shared cache (such as a list or hash table) to see if key N already exists. If found, it halts recursive branching and returns the stored value in O(1) time.
• Under the Hood: If the value is absent, the function executes its recursive transitions, aggregates the return values, and saves the result into the cache before returning it to the caller. This guarantees that every unique subproblem executes its core logic only once.
• Nuance: Remember that 'memoization' derives from writing a 'memo' (reminder note), not 'memorization'. It still utilizes system call-stack memory proportional to the maximum recursion depth.

# Top-Down DP: Memoization with O(N) time and O(N) stack/cache space
def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    # Lookup stored computation
    if n in memo:
        return memo[n]
    # Compute, store in lookup table, and return
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Key Takeaway: Top-down memoization maintains recursive structure while achieving linear time by caching every subproblem result upon first computation.

3. Bottom-Up Dynamic Programming via Tabulation

Tabulation computes solutions iteratively from the smallest base cases upward to N, completely eliminating recursion overhead and stack limits.

• Mechanism: The algorithm allocates a contiguous table sized to accommodate all subproblem states up to N and seeds the earliest positions with explicit base case values (e.g., indices 0 and 1).
• Under the Hood: An iterative loop advances through subsequent indices in topological order, computing each entry using strictly pre-calculated entries from earlier indices. Because dependencies are computed forward, no call-stack frames are created.
• Best Practice: Use bottom-up tabulation when the dependency order between subproblems is strictly sequential or forward-moving, as it reduces runtime overhead and simplifies space-reduction refactors.

# Bottom-Up DP: Tabulation with O(N) time and iterative state array
def fib_bottom_up(n):
    if n <= 1:
        return n
    # Initialize table sized for N + 1 entries
    table = [0] * (n + 1)
    table[1] = 1
    # Iteratively resolve dependencies from base cases up to n
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]

Key Takeaway: Tabulation iteratively fills a state array from base cases to N, removing call-stack overhead.

Topics Covered in Dynamic Programming Basics

1. Defining Dynamic Programming (0:09 - 0:27) — Dynamic programming optimizes algorithms with overlapping subproblems by storing intermediate results.
2. Three Steps of DP (1:24 - 1:53) — The standard DP workflow transitions from naive recursion to memoization and finally to bottom-up tabulation.
3. Inefficient Recursive Solution (1:57 - 3:16) — Naive recursion on Fibonacci generates an exponential O(2^N) call tree due to redundant subproblems.
4. Top-Down Memoization (3:16 - 4:54) — Adding a memo cache intercepts redundant recursive calls to retrieve precomputed values.
5. Memoization Complexity Analysis (4:54 - 6:45) — Caching subproblems reduces total unique function evaluations to achieve linear O(N) time complexity.
6. Bottom-Up Tabulation (7:36 - 8:34) — An iterative loop builds an array sequentially from base cases to N in linear O(N) time.

DSA for Interviews Cheat Sheet

• memo = [None] * (n + 1) — Initializes a fixed-size memoization lookup table

  memo = [None] * (n + 1)
  

• if memo[n] is not None: return memo[n] — Returns cached subproblem result immediately

  if memo[n] is not None:
      return memo[n]
  

• memo[n] = recursive_call() — Stores computed subproblem result into cache

  memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
  

• table = [0] * (n + 1) — Allocates bottom-up tabulation array

  dp = [0] * (n + 1)
  

• for i in range(2, n + 1): — Iterates forward to compute states sequentially

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

Comparison Table

Common Pitfalls

• Mistake: Confusing memoization with human memorization. Avoid: Treat memoization strictly as caching function outputs by input arguments in a lookup table.
• Mistake: Omitting base cases before cache checks in memoized recursion. Avoid: Explicitly define and return base cases or seed cache indices before evaluating transitions.
• Mistake: Neglecting call-stack depth limits during deep top-down recursion. Avoid: Convert deep top-down recursive solutions to iterative bottom-up tabulation loops.

FAQs

• What is the difference between memoization and memorization? Memoization refers to storing programmatic computation results in a cache, whereas memorization refers to committing information to human memory.
• Why does Dynamic Programming reduce Fibonacci complexity from O(2^N) to O(N)? It ensures that each of the N subproblems is evaluated only once instead of recalculating identical recursive subtrees exponentially.
• When is bottom-up tabulation preferred over top-down memoization? Tabulation is preferred when state dependencies are forward-moving and known, as it avoids function call overhead and recursion stack overflow.