Dynamic Programming Guide: From Basics to Mastery

Table of Contents

1. Prerequisites
2. Understanding DP
3. Problem-Solving Framework
4. Interview Hacks
5. Common Patterns
6. Optimization Techniques

Prerequisites

Core Concepts You Must Master

1. Arrays & Their Algorithms

   • Two-pointer technique
   • Sliding window
   • Prefix sum arrays (crucial for DP optimizations!)

2. Data Structures

   • Hashmaps (for memoization)
   • Binary trees
   • Graphs (especially DFS)

3. Problem-Solving Techniques

   • Backtracking
   • Binary search
   • Recursion fundamentals

Problem-Solving Framework

1. The 5-Step Approach

1. Identify if it's a DP problem
   - Look for overlapping subproblems
   - Check if optimal substructure exists
   
2. Define state variables
   - What changes between recursive calls?
   - Usually corresponds to input parameters
   
3. Write recurrence relation
   - Express problem in terms of smaller subproblems
   
4. Define base cases
   - Smallest possible inputs
   - Edge cases
   
5. Implement solution
   - Start with recursion
   - Add memoization
   - Convert to bottom-up if needed

2. Implementation Template (Python)

# Top-Down Template
def dp_function(input_params):
    cache = {}  # or @lru_cache decorator
    
    def dfs(*states):
        # 1. Base cases
        if base_case:
            return base_value
            
        # 2. Check cache
        if states in cache:
            return cache[states]
            
        # 3. Recurrence relation
        result = ...  # compute using smaller subproblems
        
        # 4. Cache and return
        cache[states] = result
        return result
    
    return dfs(initial_states)

Interview Hacks

1. Quick Pattern Recognition

• If input is sequence: Try 1D DP
• If input is two sequences: Try 2D DP
• If asking for ways to do something: Try counting DP
• If asking for max/min: Try optimization DP

2. Time-Saving Tricks

# 1. Use Python's built-in cache
from functools import lru_cache

@lru_cache(None)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

# 2. Quick 2D DP initialization
dp = [[0] * (cols + 1) for _ in range(rows + 1)]

# 3. Initialize with infinity for min problems
dp = [[float('inf')] * (cols + 1) for _ in range(rows + 1)]

3. Space Optimization Patterns

• 1D DP: Often can use two variables instead of array
• 2D DP: Often can use two rows instead of matrix

# Before optimization
dp = [0] * n

# After optimization
prev, curr = 0, 0
for i in range(n):
    prev, curr = curr, new_value

Common Patterns

1. Sequence Patterns

• Prefix/Suffix: Store results for prefixes/suffixes
• Window: Fixed or variable size window
• Two Sequences: Compare/merge two sequences

2. Matrix Patterns

• Path Problems: Count paths or find optimal path
• Region Problems: Find regions with properties
• Cut Problems: Optimal way to cut/partition

3. State Transition Patterns

1. Pick or Skip
   dp[i] = max(dp[i-1], dp[i-2] + nums[i])

2. Multiple Choice
   dp[i] = max(dp[i-1] + choice1, 
               dp[i-2] + choice2,
               dp[i-3] + choice3)

3. Matching
   dp[i][j] = dp[i-1][j-1] if match
             else min(insert, delete, replace)

Optimization Techniques

1. State Reduction

• Remove redundant states
• Combine related states
• Use bit manipulation for state compression

2. Memory Optimization

• Rolling array technique
• State compression
• Space-optimized versions

3. Time Optimization

• Precalculation and lookup tables
• Monotonic stack/queue optimizations
• Binary search optimization

Happy coding! 🚀