Dynamic Programming

---
name: Dynamic Programming
description: Optimization technique that solves complex problems by breaking them into overlapping subproblems, solving each once, and storing results to avoid redundant computation
---

# Dynamic Programming Algorithm Paradigm

## What It Is
An optimization technique that solves complex problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the results to avoid redundant computation. Unlike divide-and-conquer where subproblems are independent, DP exploits the overlap by remembering solutions (memoization or tabulation) to transform exponential-time recursive algorithms into polynomial-time solutions.

## When to Use It
- Problem has **overlapping subproblems** (same subproblem solved multiple times)
- Problem exhibits **optimal substructure** (optimal solution contains optimal solutions to subproblems)
- Recursive solution exists but has exponential time due to repeated computation
- Need to find optimal value (min/max) or count all possible solutions
- Problem involves sequences, trees, graphs with state-dependent decisions
- Trade space for time is acceptable (store intermediate results)

## Execution Steps

### 1. Clarify the State
Identify what variables fully describe a subproblem. State should be minimal but complete - enough to uniquely identify each subproblem. Common state patterns: position in array, remaining capacity, substring boundaries, node in graph.

**Action**: Ask "What parameters change in the recursion?" Write state as `dp[i]`, `dp[i][j]`, or `dp[state_tuple]`. Example: Fibonacci → `dp[n]`; Knapsack → `dp[item][capacity]`.

### 2. Define the Recurrence (State Transition)
Express the solution for state `dp[i]` in terms of smaller/simpler states. This is the heart of DP. Identify the decision at each step and how choices affect the state.

**Action**: Write the recurrence relation mathematically. Example: `dp[i] = min(dp[i-1] + cost1, dp[i-2] + cost2)`. Ensure base cases are clearly defined (typically `dp[0]` or boundary conditions).

### 3. Choose Implementation Approach
**Top-Down (Memoization)**: Start from the problem, recurse naturally, cache results in a memo table. Easier to write, only computes needed subproblems.

**Bottom-Up (Tabulation)**: Start from base cases, iteratively fill table in topological order. More efficient (no recursion overhead), easier to optimize space.

**Action**: For interview/rapid prototyping → top-down. For production/performance → bottom-up. Consider space optimization (often reduce from O(n²) to O(n) by keeping only last row).

### 4. Identify the Choices
At each state, what decisions can you make? For optimization problems: which option to take? For counting: how many ways to proceed? Choices determine the recurrence structure.

**Action**: List all valid transitions from current state. Example: Coin change → try each coin denomination; Longest increasing subsequence → include or skip current element.

### 5. Code the Solution
Implement the recurrence with proper base cases. For top-down: add memoization decorator or explicit cache checks. For bottom-up: initialize table, iterate in correct order (ensure dependencies computed first), extract final answer.

**Action**: Write base case first, then recursive/iterative logic, finally return `dp[target_state]`. Test with small examples manually before running.

### 6. Analyze and Optimize
Calculate time complexity (usually O(num_states × transitions_per_state)) and space complexity. Look for space optimization opportunities: rolling arrays, state compression, dimension reduction.

**Action**: Measure runtime on test cases. Profile memory usage. Apply space optimizations if needed (e.g., Fibonacci from O(n) space to O(1)).

## Real-World Applications

**Finance & Operations Research**
- Portfolio optimization: maximize returns given constraints
- Resource allocation: knapsack variants for budget distribution
- Inventory management: optimal ordering policies over time

**Bioinformatics**
- Sequence alignment (Needleman-Wunsch, Smith-Waterman): DNA/protein matching
- RNA folding prediction: secondary structure optimization
- Phylogenetic tree construction: evolutionary distance minimization

**Text Processing**
- Edit distance (Levenshtein): spell checkers, DNA matching, diff tools
- Longest common subsequence: version control, plagiarism detection
- Word break problem: natural language processing, search query parsing

**Game Theory & AI**
- Optimal game strategy: chess endgames, poker decision trees
- Reinforcement learning: value iteration, policy optimization (Bellman equations)
- Path planning: robot navigation with state-dependent costs

**Computer Graphics & Vision**
- Image segmentation: seam carving, optimal path finding
- Video encoding: motion estimation, compression optimization
- Texture synthesis: dynamic texture generation

**Compiler Optimization**
- Code generation: register allocation, instruction scheduling
- Matrix chain multiplication: optimal parenthesization for expression evaluation
- Optimal binary search trees: minimize expected search time

## Anti-Patterns

**Using DP when subproblems don't overlap** → Wastes space storing unused results; use divide-and-conquer instead.

**Wrong state definition** → Leads to incorrect recurrence or exponential state space; rethink what truly defines a subproblem.

**Missing base cases** → Causes infinite recursion or index errors; always handle boundary conditions explicitly.

**Computing states in wrong order (bottom-up)** → Accesses uninitialized values; ensure topological order respects dependencies.

**Not checking for optimality structure** → DP won't work if optimal solution doesn't contain optimal subsolutions; verify this property first.

**Over-engineering the recurrence** → Including unnecessary state dimensions bloats space complexity; keep state minimal.

## Success Metrics
- Time complexity reduction from exponential to polynomial (e.g., O(2ⁿ) → O(n²))
- Correctness on all test cases including edge cases (empty input, single element)
- Space efficiency (can O(n²) be reduced to O(n)?)
- Code clarity (recurrence relation obvious from implementation?)
- Performance on large inputs (n=10,000+) vs. recursive baseline

## Related Frameworks
- **Divide and Conquer**: For non-overlapping subproblems (convert DP to D&C by removing memoization)
- **Greedy Algorithms**: When local optimal choices suffice (DP guarantees global optimum)
- **Backtracking**: For constraint satisfaction without optimization
- **Memoization Pattern**: General caching technique beyond DP
- **Bellman-Ford, Dijkstra**: Graph shortest paths using DP principles

## Common Pitfalls
- Forgetting to initialize DP table with sentinel values (infinity for min, zero for max)
- Off-by-one errors in state indices (especially for substrings/subarrays)
- Not handling negative numbers/weights when problem assumes non-negative
- Confusing "optimal substructure" with "subproblem independence" (DP needs former, not latter)
- Implementing top-down without memoization (defeating the purpose)
- Using recursion with memoization for extremely deep problems (stack overflow)

## Tools & Resources
- **Visualization**: Dynamic Programming Visualizer (algorithm-visualizer.org), LeetCode's DP Explorer
- **Practice Platforms**: LeetCode (DP tag ~400 problems), Codeforces DP category, Project Euler
- **Books**: "Dynamic Programming for Coding Interviews" (Meenakshi), "Algorithms" (Dasgupta, Papadimitriou, Vazirani)
- **Pattern Guides**: "Dynamic Programming Patterns" (14 common patterns: Fibonacci, 0/1 Knapsack, Unbounded Knapsack, LCS, LIS, Palindromes, etc.)
- **Debugging**: Print DP table after computation to verify values, use small test cases (n≤5) for manual checking

## Classic Problem Patterns

**Linear DP**: Fibonacci, climbing stairs, house robber (1D state, O(n))

**Grid DP**: Unique paths, minimum path sum, edit distance (2D state, O(n×m))

**Knapsack Variants**: 0/1 knapsack, unbounded knapsack, subset sum (2D → 1D optimization possible)

**Interval DP**: Matrix chain multiplication, palindrome partitioning (O(n³) with 2 endpoints as state)

**Tree DP**: House robber III, binary tree cameras (state = node + subtree status)

**Bitmask DP**: Traveling salesman, subset enumeration (state = visited set as bitmask)

---
*Framework Type*: Algorithm Design Paradigm
*Domain*: Computer Science, Optimization
*Practitioner Score*: 10/10 - Essential for technical interviews, powers production systems at scale
*Complexity*: Medium-High - Requires recurrence relation insight and state design skills
*Prerequisites*: Recursion, mathematical induction, basic combinatorics, time/space complexity analysis