Dynamic Programming

Dynamic Programming (DP) is a powerful algorithmic technique used to solve complex problems by breaking them down into simpler overlapping subproblems. It’s essential for technical interviews at FAANG companies and typically appears in 30-40% of coding interview problems.

Dynamic Programming combines two key concepts:

• Overlapping Subproblems: Solutions to larger problems depend on solutions to smaller subproblems that are solved multiple times
• Optimal Substructure: The optimal solution can be constructed from optimal solutions of its subproblems

Unlike recursion, DP stores results of subproblems to avoid redundant calculations, achieving significant performance improvements.

Real-World Analogy

Imagine you’re a librarian organizing books on shelves. You need to find the best arrangement that minimizes the total walking distance for patrons. Instead of trying every possible arrangement (which would take forever), you solve smaller subproblems:

1. What’s the best arrangement for the first shelf?
2. What’s the best arrangement for the first two shelves?
3. And so on…

Each time you add a new shelf, you only need to consider the best arrangements from the previous step, not all possible arrangements from scratch. This is exactly how DP works - building optimal solutions incrementally.

Visual Explanation

Let’s visualize how DP works with the Fibonacci sequence:

  graph TD
    A["fib(5)"] --> B["fib(4)"]
    A --> C["fib(3)"]
    B --> D["fib(3)"]
    B --> E["fib(2)"]
    C --> F["fib(2)"]
    C --> G["fib(1)"]
    D --> H["fib(2)"]
    D --> I["fib(1)"]
    E --> J["fib(1)"]
    E --> K["fib(0)"]
    F --> L["fib(1)"]
    F --> M["fib(0)"]

    style A fill:#e1f5fe
    style B fill:#e8f5e8
    style C fill:#e8f5e8
    style D fill:#fff3e0
    style E fill:#fff3e0
    style F fill:#fff3e0

Notice how fib(3) and fib(2) are computed multiple times in the recursive approach. DP eliminates this redundancy by storing results.

Two Main Approaches

1. Top-Down (Memoization)

Start from the original problem and break it down recursively, caching results as you go.

Key Benefits:

• Natural recursive thinking
• Only computes needed subproblems
• Easy to implement with recursion + memo cache

Key Drawbacks:

• Recursion depth limits
• Function call overhead

2. Bottom-Up (Tabulation)

Start from base cases and build up to the final solution iteratively.

Key Benefits:

• No recursion limits
• Better space optimization potential
• Often more intuitive for certain problems

Key Drawbacks:

• May compute unnecessary subproblems
• Can be harder to think about recursively

Common DP Problem Types

1. 1D Array DP Problems

• House Robber: Linear array with adjacent constraints
• Jump Game: Reach end with minimum/maximum jumps
• Decode Ways: Count ways to decode string
• Unique Paths: Grid path counting

2. 2D Matrix DP Problems

• Minimum Path Sum: Find path with minimum sum
• Edit Distance: String transformation cost
• Maximal Rectangle: Largest rectangle in binary matrix
• Dungeon Game: Minimum health to reach end

3. String DP Problems

• Longest Palindromic Substring: Expand around centers
• Word Break: Can string be segmented into dictionary words
• Distinct Subsequences: Count subsequences in string
• Regular Expression Matching: Pattern matching

4. Tree DP Problems

• Diameter of Binary Tree: Longest path in tree
• Maximum Path Sum: Path with maximum sum
• House Robber III: Tree with parent-child constraints
• Binary Tree Cameras: Minimum cameras to cover tree

5. Interval DP Problems

• Matrix Chain Multiplication: Optimal multiplication order
• Burst Balloons: Maximum coins from bursting balloons
• Stone Game: Game theory on linear array
• Palindrome Partitioning: Minimum cuts for palindromes

When to Use This Pattern

Use Dynamic Programming when you can answer “YES” to these questions:

• Can the problem be broken down into smaller subproblems?
• Do subproblems overlap? (Same subproblem solved multiple times)
• Does the problem have optimal substructure? (Optimal solution built from optimal sub-solutions)
• Can you cache subproblem results? (Memoization or tabulation possible)
• Are you looking for an optimal solution? (Min/max, count ways, not just feasibility)

DP is appropriate when:

• Problem can be broken into smaller subproblems
• Subproblems overlap (optimal substructure)
• Subproblem solutions can be cached
• Need optimal solution (not just feasibility)

DP might not be needed when:

• No overlapping subproblems (greedy works)
• Problem can be solved more simply
• Space constraints are too tight
• Time complexity requirements are strict

Complexity Analysis

Time Complexity

• Naive Recursion:
  O(2^N)
  (exponential)
• Memoization:
  O(N)
  (linear for simple cases)
• Tabulation:
  O(N)
  (linear for simple cases)
• 2D DP:
  O(N²)
  (quadratic for matrix problems)

Space Complexity

• Naive Recursion:
  O(N)
  (call stack)
• Memoization:
  O(N)
  (memo table)
• Tabulation:
  O(N)
  (DP table)
• Space Optimized:
  O(1)
  (constant space)

Interview Tips

1. Identify DP Problems

• Optimization problems (min/max, count ways)
• Combinatorial problems
• Sequence/string problems
• Problems with multiple constraints

2. Define State Clearly

• What variables change in subproblems?
• What constitutes a subproblem’s state?
• How to compute final answer from states?

3. Choose State Representation

• Arrays, maps, or custom objects
• Minimize state dimensions
• Consider memory constraints

4. Handle Base Cases

• Smallest possible inputs
• Boundary conditions
• Invalid states

5. Transition Between States

• Express recurrence relations
• Ensure all subproblem dependencies met
• Avoid circular dependencies

Common Mistakes

1. Wrong State Definition: Missing variables or incorrect bounds
2. Base Case Errors: Incorrect initialization or boundary values
3. Transition Function Bugs: Wrong recurrence relations
4. Iteration Order Issues: Computing states before dependencies
5. Index Errors: Off-by-one in array indexing

Next Steps

Ready to practice? Check out our curated problems and code templates to reinforce your understanding.