dynamic-programming

# 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