The Four Core Patterns of DP
Understanding DP Patterns
Dynamic Programming can be applied to a wide variety of problems, but most of them follow one of these four core patterns.
Each pattern represents a different way of thinking about and applying DP to solve problems.
Learning Objective
Understand the core patterns of dynamic programming and how they can be applied to solve different types of problems.
The Four Core Patterns of Dynamic Programming
While dynamic programming can be applied to many different problems, most solutions follow one of these four core patterns. Understanding these patterns will help you recognize when and how to apply DP to new problems.
Memoization Pattern
Optimize recursive solutions by storing and reusing results of subproblems, following a top-down approach.
Examples: Fibonacci, Longest Common Subsequence, Coin Change
Tabulation Pattern
Build solutions iteratively using tables to store results of subproblems, following a bottom-up approach.
Examples: Knapsack, Longest Increasing Subsequence, Edit Distance
State Compression Pattern
Optimize space usage by storing only the necessary states for computation, often reducing dimensionality.
Examples: Optimized Fibonacci, Space-Optimized Knapsack, 2D DP with 1D Arrays
Decision Making Pattern
Make optimal choices at each step to build the overall optimal solution, often involving multiple options.
Examples: Buy/Sell Stock, House Robber, Jump Game
Choosing the Right Pattern
When faced with a problem that might be solved using dynamic programming, ask yourself these questions to identify the most appropriate pattern:
For Memoization Pattern
"Is the problem naturally recursive? Do I need to avoid recalculating the same subproblems? Is a top-down approach more intuitive for this problem?"
For Tabulation Pattern
"Can I build the solution iteratively from base cases? Do I need to avoid recursion stack overflow? Is a bottom-up approach more efficient for this problem?"
For State Compression Pattern
"Do I need to optimize space usage? Can I reduce the dimensionality of my DP table? Do I only need a few previous states to compute the current state?"
For Decision Making Pattern
"Does the problem involve making choices at each step? Do I need to find the optimal sequence of decisions? Can the problem be broken down into a series of choices?"