dp-patternslisted

# Dynamic Programming Patterns This reference covers eight foundational dynamic programming patterns commonly encountered in algorithmic problem solving. Each pattern includes recognition signals to identify when a problem maps to the technique, a working Python template, and specific edge cases and mistakes to watch for. Load this skill when solving optimization, counting, or subsequence problems that exhibit optimal substructure and overlapping subproblems. ## General DP Approach Before selecting a specific pattern, apply this checklist: 1. **Identify the state**: What information do you need to uniquely describe a subproblem? (index, remaining capacity, bitmask of visited nodes) 2. **Define the recurrence**: How does the answer for the current state relate to answers for smaller states? 3. **Establish base cases**: What are the trivial subproblems with known answers? 4. **Determine iteration order**: Ensure every state is computed before it is needed (bottom-up) or use memoization (top-down) 5. **Optimize space**: If dp[i] depends only on dp[i-1] (or a small window), use rolling arrays instead of the full table ## Pattern Recognition Table | Trigger Signals | Technique | Typical Complexity | |---|---|---| | "count the number of ways", "how many distinct paths" | Fibonacci / Climbing Stairs | O(N) time, O(1) space | | "maximize value with weight limit", "partition into two equal subsets" | 0/1 Knapsack | O(N * W) time, O(W) space | | "longest common subsequence", "min