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

Dynamic Programming (DP) is 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.

---

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 first i items).
2. Define the Transition: What is the recurrence relation? (dp[i] = …).
3. Identify Base Cases: What is the smallest subproblem? (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? (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.

Calculate F(n):

---

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.”

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.”

---

6. Implementation: Fibonacci (Java & Go)

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];
}

func Fib(n int) int {
  if n <= 1 { return n }
  dp := make([]int, n+1)
  dp[0], dp[1] = 0, 1
  for i := 2; i <= n; i++ {
    dp[i] = dp[i-1] + dp[i-2]
  }
  return dp[n]
}

---

7. Summary

• Time Complexity: Reduces from O(2^N) to O(N).
• Space Complexity: O(N) for the table (can often be optimized to O(1)).

---

8. 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.

Mathematical Anchor: Bellman Equation

Most DP problems can be described as: OPT(state) = max / min { OPT(subproblem) + cost } Finding the “state” is 90% of the work in DP.