Introduction to Dynamic Programming

[!NOTE] This module explores the core principles of Introduction to Dynamic Programming, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. The Hook: Overlap and Optimization

Imagine you are asked to sum the following numbers: 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = ?

You count them and answer 8. Now, imagine another + 1 is appended to the end of the equation. Do you recount everything from the start? No. You instantly know it’s 9 because you remembered the previous result.

Dynamic Programming (DP) is exactly this: Recursion + Caching.

It is an optimization technique used to solve complex problems by breaking them down into simpler, overlapping subproblems. We “trade space for time” by storing results to avoid re-computing them. If a problem can be solved optimally by breaking it into subproblems, and those subproblems are evaluated multiple times, DP is the perfect tool.

2. The 4 Pillars of DP Mastery

Pillar Focus Why it matters
1. Intuition Recursive Structure Identifying if a problem has “Optimal Substructure”.
2. Rigor 5-Step Framework Systematically deriving the solution instead of “guessing” the table.
3. Hardware Memoization vs Tabulation Understanding stack depth (Top-Down) vs cache locality (Bottom-Up).
4. Optimization State Compression Reducing O(N2) space to O(N) or O(1) by identifying dependencies.

3. The 5-Step DP Framework

Don’t start coding immediately. Follow this blueprint for every DP problem:

  1. Define the State: What do the indices represent? (e.g., dp[i] is the max profit using the first i items).
  2. Define the Transition: What is the recurrence relation? (e.g., dp[i] = dp[i-1] + dp[i-2]).
  3. Identify Base Cases: What is the smallest subproblem? (e.g., dp[0] = 0).
  4. Order of Computation: Do we go from 0 -> N or N -> 0?
  5. Identify the Final Goal: Where is the answer? (e.g., dp[N] or max(dp)).

4. Interactive: Recursion vs. DP

See the difference between the explosive growth of a naive recursion tree and the linear efficiency of a DP table. Naive recursion computes the same subproblems repeatedly, while tabulation simply reads previous results.

Calculate F(n):

Recursion Tree (Top-Down without Memoization)

Tabulation (Bottom-Up Array)

5. The Two Approaches

A. Top-Down (Memoization)

Start from the goal and work backwards. Use recursion and a “memo” table (HashMap/Array) to store results.

  • Intuition: “I’ll solve the big problem, but I’ll remember the answer to every small piece I unlock.”
  • Hardware Reality: Uses the call stack. Deep recursion can lead to StackOverflowError. Each recursive call carries overhead, making it slightly slower than tabulation in practice.

B. Bottom-Up (Tabulation)

Start from the base cases and build up. Use a table (Array) and iteration.

  • Intuition: “I’ll solve all the smallest pieces first, then use them like LEGOs to build the final answer.”
  • Hardware Reality: Highly efficient use of CPU cache locality because array elements are accessed sequentially. Avoids function call overhead. Usually preferred in production systems.

6. Implementation: Fibonacci

Let’s look at how Fibonacci evolves from naive recursion, to tabulation, and finally to optimized state compression.

Approach 1: Naive Recursion (Too Slow)

Time: O(2N) | Space: O(N)

public int fib(int n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

Approach 2: Bottom-Up Tabulation

Time: O(N) | Space: O(N)

public int fib(int n) {
  if (n <= 1) return n;
  int[] dp = new int[n + 1];
  dp[0] = 0; dp[1] = 1;
  for (int i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
  }
  return dp[n];
}

Approach 3: State Compression (Optimized)

Notice how calculating dp[i] only ever requires dp[i-1] and dp[i-2]. The rest of the array is essentially wasted space! We can reduce O(N) space to O(1) by only tracking the last two values.

Time: O(N) | Space: O(1)

public int fib(int n) {
  if (n <= 1) return n;
  int prev2 = 0; // Represents dp[i-2]
  int prev1 = 1; // Represents dp[i-1]

  for (int i = 2; i <= n; i++) {
    int current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}

func Fib(n int) int {
  if n <= 1 { return n }
  prev2, prev1 := 0, 1
  for i := 2; i <= n; i++ {
    current := prev1 + prev2
    prev2 = prev1
    prev1 = current
  }
  return prev1
}

7. Deep Dive Strategy Lab: DP Basics

Intuition Through Analogy

Think of this like budget planning across months. Instead of recalculating your total savings from scratch every single day, you just take yesterday’s balance and add today’s income. This avoids redundant effort.

Mathematical Anchor: Bellman Equation

Most DP problems can be described structurally as: OPT(state) = max / min { OPT(subproblem) + cost }

Finding the “state” and the “transition function” is 90% of the work in DP.

Why not always use Memoization?

While Memoization is generally easier to write if you already have the recursive relationship, Tabulation allows for State Compression. If your DP transition only relies on the previous row or previous two variables, you can discard the full N x M matrix and use just 1 x M space. This is a common and critical optimization step in interviews.