Dynamic Programming

Optimal Substructure, Overlapping Subproblems, Memoization vs Tabulation

Dynamic Programming Principles

Key Concepts:

  • When to use DP: Optimal substructure + overlapping subproblems
  • Optimal Substructure: Optimal solution contains optimal solutions to subproblems
  • Overlapping Subproblems: Same subproblems computed multiple times
  • Memoization: Top-down with caching (recursive)
  • Tabulation: Bottom-up with table (iterative)
  • Steps: (1) Define subproblems, (2) Relate subproblems (recurrence), (3) Compute bottom-up or memoize top-down

Video Recommendations:

🎥 MIT OCW - Dynamic Programming Overview (48 min - comprehensive) 🎥 CS Dojo - DP Intro (11 min)

DP vs Greedy vs Divide & Conquer:

  • Greedy: Makes one choice, never reconsiders (fast, doesn't always work)
  • D&C: Independent subproblems, no overlap
  • DP: Overlapping subproblems, tries all choices, saves results

Classic DP Problems (Examples to Study)

Common Patterns:

  • Rod Cutting: Max revenue by cutting rod into pieces
  • Matrix Chain Multiplication: Optimal parenthesization for min scalar multiplications
  • Longest Common Subsequence (LCS): Longest subsequence common to two sequences
  • Optimal Binary Search Trees: BST with min expected search cost
  • 0/1 Knapsack: Max value with weight constraint (items can't be split)

Study Approach:

For each problem: (1) Understand the problem, (2) Identify subproblem structure, (3) Write recurrence relation, (4) Understand base cases, (5) Trace through small example.

Rod Cutting Example

Problem:

Given rod of length n and prices p[i] for lengths i=1..n, find maximum revenue by cutting rod.

Recurrence:

r[n] = max(p[i] + r[n-i]) for i = 1 to n
r[0] = 0 (base case)
  • Subproblems: r[i] = max revenue for rod of length i
  • Time: O(n²) with DP, exponential without

Matrix Chain Multiplication

Problem:

Given chain of matrices, find optimal parenthesization to minimize scalar multiplications.

Key Points:

  • Not computing product! Just finding optimal order
  • Subproblems: m[i,j] = min cost to multiply matrices i through j
  • Recurrence: m[i,j] = min{m[i,k] + m[k+1,j] + p[i-1]·p[k]·p[j]} for k=i to j-1
  • Time: O(n³)

Video Recommendations:

🎥 Abdul Bari - Matrix Chain Multiplication (29 min)

Longest Common Subsequence (LCS)

Problem:

Find longest subsequence common to two sequences (not necessarily contiguous).

Recurrence:

If X[i] == Y[j]: LCS[i,j] = LCS[i-1,j-1] + 1
Else: LCS[i,j] = max(LCS[i-1,j], LCS[i,j-1])
  • Table: 2D array, size (m+1) × (n+1)
  • Time: O(mn)
  • Space: O(mn), can be optimized to O(min(m,n))

Video Recommendations:

🎥 Back to Back SWE - LCS (15 min)

DP Problem-Solving Template:

  1. Define subproblems: What does DP[i] or DP[i][j] represent?
  2. Find recurrence: How to compute DP[i] from smaller subproblems?
  3. Base cases: What are the initial/boundary values?
  4. Computation order: Bottom-up or top-down? What order to fill table?
  5. Reconstruct solution: How to trace back to get actual solution (not just optimal value)?

Additional DP Resources:

Check your problem sets (ps6-ps7) for specific DP problems covered in your course. Practice is key for DP!