DP vs. Greedy: The Core Tradeoff
Before diving into the patterns, you must understand the key difference between Greedy and Dynamic Programming algorithms. Both are optimization techniques, but they make choices in opposite ways:
• 🏃♂️ Greedy Algorithms: Make the locally optimal choice at each step (the choice that looks best *right now*) and never look back or change their mind. It is incredibly fast, but only works if making local choices guarantees a globally correct answer.
• 🧠 Dynamic Programming: Does not assume local choices lead to the global best. Instead, DP systematically evaluates all possible paths, solves their subproblems, and chooses the absolute best global path. To avoid redundant calculation, it remembers the answers to subproblems in a cache.
💡 Example: Making Change for 6 Cents using Coins [1, 3, 4]
• Greedy Approach: Grabs the largest possible coin first: 4c. Remaining change is 2c. Grabs 1c, then another 1c. Total: 3 coins ([4, 1, 1]).
• DP Approach: Evaluates all options. It tries starting with 4c (needs 3 coins), but also tries starting with 3c (leaving 3c, which takes exactly one 3c coin). It finds the global optimum: 2 coins ([3, 3]).
Greedy gets trapped by local decisions. DP finds the true global optimum.
Solving overlap, remembering solutions
"Dynamic Programming is just recursion with a cache. If you solve the same subproblem twice, you're doing it wrong."
Dynamic Programming is a method for solving complex problems by breaking them down into simpler, overlapping subproblems. Instead of solving these subproblems repeatedly, we solve each subproblem exactly once and store the result in a table (memory) for future lookup.
1. Overlapping Subproblems
The problem must break down into smaller tasks that are solved repeatedly. If you solve fib(3) multiple times while calculating fib(5), you have overlapping subproblems. This is where the cache saves time.
2. Optimal Substructure
The optimal solution to the main problem must be constructible from the optimal solutions of its subproblems. For example, the shortest path from A to C through B is simply the shortest path A -> B combined with the shortest path B -> C.
⚔️ DP vs. Divide & Conquer
Both techniques break problems down into subproblems, but there is a crucial difference:
• Divide & Conquer (like Merge Sort or Quick Sort) splits a problem into independent subproblems (sorting the left half has nothing to do with sorting the right half). There is no overlapping work, so caching is useless.
• Dynamic Programming handles subproblems that overlap and share common work. Since they share work, caching results is the key to reducing exponential recursion into linear or polynomial time.
Interactive Demo: Naive Recursion vs. Memoization (DP)
Call fib(5).
How to solve any DP problem
Instead of jumping to code, structure your thoughts into four precise steps:
1. State Definition
What represents a subproblem? (e.g. dp[i] = answer for prefix of length i). It acts as your resume/save point.
2. Transition Equation
The recurrence relation. How does the solution at the current state combine solutions from smaller states?
3. Base Cases
The simplest inputs whose answers are trivial and can be hardcoded immediately (e.g., dp[0] = 0).
4. Computation Order
How to evaluate? Either Top-Down (recursion with a memo map) or Bottom-Up (iterative loops filling an array).
The 9 Core DP Patterns
Below is the sequential catalog of the 9 core Dynamic Programming patterns. For each pattern, study its mantra, transition logic, spotting clues, and proceed to the lab to simulate the representative problems.
Linear Progression
"Build the solution step-by-step from base cases forward."
Representative Problem: House Robber
You are planning to rob houses along a street. If you rob two adjacent houses, the security system will trigger. How do you maximize your profit?
🧠 What is the memory? (The State)
dp[i] = The maximum money you can rob from the first i houses without triggering alarms.
🤔 The Core Decision (Plain English)
At the current house i, you must decide between two options: 1. Skip this house: Your profit remains the same as what you had at the previous house (dp[i-1]). 2. Rob this house: You take today's money + the max profit you had 2 houses ago (price[i] + dp[i-2]). You choose the option that yields more money.
Labeled Math Equation
🔎 Pattern Signals (When to use it?)
- 📈Linear input structure: You are given a 1D array or a single string of length N.
- 🔗Adjacent dependencies: To compute the best answer at index i, you only need the answers from i-1 or i-2 (e.g. taking 1 or 2 steps, robbing or skipping the previous house).
- ❌No combinations or subsets: You do not need to compare two sequences or track visited elements.
Interactive Walkthrough: Table filling
Base cases: dp[0] = 1 (0 stairs, 1 way — do nothing), dp[1] = 1 (1 stair, 1 way).
🚀 Practice Simulations & Detailed Derivations:
Binary Choice (Take / Not Take)
"For each item, make a binary choice: spend capacity to take, or skip to preserve it."
Representative Problem: 0/1 Knapsack
You have a backpack with a weight capacity of 10kg, and a list of items (each with a weight and a value). How do you choose items to get the maximum value without breaking your backpack?
🧠 What is the memory? (The State)
dp[i][w] = The maximum value you can get using only the first i items, with exactly w kg of capacity left in your backpack.
🤔 The Core Decision (Plain English)
At item i with remaining capacity w, you make a binary choice: 1. Skip the item: Your value is whatever you had with the previous i-1 items (dp[i-1][w]). 2. Take the item: You get its value, but you must have had enough capacity to carry it (value[i-1] + dp[i-1][w - weight[i-1]]).
Labeled Math Equation
🔎 Pattern Signals (When to use it?)
- 🎒Bounded capacity/budget: The problem specifies a maximum weight, target sum, or subset count that you cannot exceed.
- ⚖️Discrete items with weights & values: You are given a list of distinct items, each having a cost/weight and a reward/value.
- 🚫No reuse allowed: You can choose each item at most once (binary choice: take it or skip it).
🚀 Practice Simulations & Detailed Derivations:
Unbounded Choice
"Unlimited supply means current decisions can reuse the same items indefinitely."
Representative Problem: Coin Change
You want to make change for exactly 11 cents. You have coin denominations of 1c, 2c, and 5c. Each coin is available in unlimited quantities. What is the fewest number of coins needed?
🧠 What is the memory? (The State)
dp[w] = The minimum number of coins needed to make exactly w cents.
🤔 The Core Decision (Plain English)
To make w cents, you look at each available coin coin_val: Try adding coin_val to the optimal solution for making (w - coin_val) cents. This takes 1 + dp[w - coin_val] coins. You scan through all coin values and pick the minimum count.
Labeled Math Equation
🔎 Pattern Signals (When to use it?)
- 🔄Infinite supply of items: You are given items (like coins or rod lengths) that you can reuse infinitely.
- 🎯Fixed target goal: You must reach an exact target sum, weight, or capacity using the items.
- 🔀Combinations or permutations: The problem asks for the minimum items to reach the target, or the number of ways to compose it.
🚀 Practice Simulations & Detailed Derivations:
Sequence DP (Two Strings)
"Compare two strings or sequences by looking at their prefixes and suffixes."
Representative Problem: Longest Common Subsequence (LCS)
You have two strings, 'stone' and 'longest'. Find the length of the longest sequence of characters that appears in both strings in the same order (but not necessarily contiguously).
🧠 What is the memory? (The State)
dp[i][j] = Length of the longest common subsequence using the first i characters of string A and the first j characters of string B.
🤔 The Core Decision (Plain English)
Compare the current characters A[i-1] and B[j-1]: 1. If they match: You add 1 to the solution of both strings before these characters (1 + dp[i-1][j-1]). 2. If they don't match: You take the best result of either skipping the character in string A (dp[i-1][j]) or string B (dp[i][j-1]).
Labeled Math Equation
🔎 Pattern Signals (When to use it?)
- 🔤Two separate string/array inputs: The problem gives you two sequences (e.g. string A and string B).
- 📏Alignment or similarity matching: You need to compare them to find their longest common subsequence, edit distance, or determine if one is a subsequence of the other.
- ✂️Prefix/Suffix subproblems: The state is defined by comparing the prefix of length i in string A and length j in string B.
Interactive Walkthrough: Table filling
LCS of "ab" and "cab" — filled row by row.
| ∅ | c | a | b | |
| ∅ | 0 | 0 | 0 | 0 |
| a | 0 | |||
| b |
Base case: matching against an empty string always gives LCS length 0 (row 0 and column 0).
🚀 Practice Simulations & Detailed Derivations:
Coordinate State (Grid DP)
"Navigating a 2D matrix? Cell (r, c) depends on neighbors above and to the left."
Representative Problem: Unique Paths
A robot starts at the top-left cell of a 3 x 7 grid and wants to reach the bottom-right cell. It can only move Right or Down. How many unique paths can it take?
🧠 What is the memory? (The State)
dp[r][c] = The number of unique paths to reach the cell at row r and column c.
🤔 The Core Decision (Plain English)
Because the robot can only move Right or Down, it can only arrive at cell (r, c) from either the cell above it (r-1, c) or the cell to its left (r, c-1). The total paths to reach this cell is the sum of paths to those two neighbors.
Labeled Math Equation
🔎 Pattern Signals (When to use it?)
- 🏁2D coordinate grid or matrix: You are given a grid of size M x N or a triangle board.
- ⬇️➡️Restricted, acyclic movement: You start at a cell (e.g. top-left) and can only move in specific directions (e.g. Right and Down) to reach a destination.
- 💰Path optimization: You need to find the path with the minimum path sum, maximum gold gathered, or total unique paths.
🚀 Practice Simulations & Detailed Derivations:
State Toggling (Stock DP)
"Decisions depend on transition states: Holding, Sold, or Cooling Down."
Representative Problem: Best Time to Buy and Sell Stock with Cooldown
Maximize stock profit, but you cannot buy stock on the day immediately after you sell it (1-day cooldown period).
🧠 What is the memory? (The State)
dp[i][state] = The maximum profit you can make on day i, depending on whether you are currently: Holding a stock (1) or Empty/Sold (0).
🤔 The Core Decision (Plain English)
For each day, you maximize profit depending on your active states (Holding or Empty). Holding depends on staying holding or buying empty. Empty depends on staying empty or selling holding.
Labeled Math Equation
🔎 Pattern Signals (When to use it?)
- 📈Daily values with active state constraints: You are given daily stock prices, and your ability to act (buy/sell) depends on your current status.
- 🔑Explicit transition rules: You cannot buy stock if you already hold it, or you must wait (cooldown) after selling before buying again.
- 💰Multiple concurrent options: You want to maximize profit by switching between 'holding' and 'not holding' states over time.
💡 Understanding the Transition States:
🚀 Practice Simulations & Detailed Derivations:
Global Dependencies (LIS Pattern)
"Optimal decision at index i requires scanning all previous elements 0 to i-1."
Representative Problem: Longest Increasing Subsequence (LIS)
You have an array [10, 9, 2, 5, 3, 7]. Find the length of the longest subsequence where the numbers are strictly increasing. (The answer is [2, 5, 7] or [2, 3, 7] -> length 3).
🧠 What is the memory? (The State)
dp[i] = The length of the longest increasing subsequence that ends exactly with the element at index i.
🤔 The Core Decision (Plain English)
To find the longest sorted chain ending with the current number nums[i]: Scan through all previous numbers nums[j] (where j < i). If nums[j] < nums[i], it means nums[i] can extend the sorted chain ending at j. Try all such j, and choose the maximum length plus 1.
Labeled Math Equation
🔎 Pattern Signals (When to use it?)
- 🔎Subsequence order constraints: You are given a single array and need to find the longest subsequence that is sorted, increasing, or matches a specific condition.
- 🌐Non-local dependencies: To find the optimal transition at index i, you cannot just look at i-1. You must scan every single element from 0 to i-1 to see which ones can precede index i.
🚀 Practice Simulations & Detailed Derivations:
Range Expansion (Interval DP)
"Solve for small ranges [i, j], then expand outward to calculate larger intervals."
Representative Problem: Burst Balloons
You have a row of balloons, e.g. [3, 1, 5, 8]. Popping balloon i gives you coins equal to balloon[i-1] * balloon[i] * balloon[i+1]. What is the maximum coins you can get by popping all balloons?
🧠 What is the memory? (The State)
dp[i][j] = The maximum coins you can collect by popping all balloons in the sub-range from index i to index j.
🤔 The Core Decision (Plain English)
To solve for the range [i, j], we try making each balloon k (where i <= k <= j) the LAST balloon to pop in this range. Popping balloon k last divides the problem into popping balloons to its left (dp[i][k-1]), popping balloons to its right (dp[k+1][j]), and popping k itself.
Labeled Math Equation
🔎 Pattern Signals (When to use it?)
- 🪵Merging or splitting adjacent elements: You are given an array, and you can merge adjacent items, split ranges, or fold elements.
- 🏷️Cost depends on active range: The cost of merging elements depends on the boundary values of the sub-array [i, j].
- ✂️All split points matter: Solving for range [i, j] requires splitting it at every possible index k (i <= k < j) and taking the optimal result.
🚀 Practice Simulations & Detailed Derivations:
Subset Tracking (Bitmask DP)
"Use a binary integer (bitmask) to represent the set of visited elements or states."
Representative Problem: Traveling Salesperson Problem (TSP)
A salesperson must visit 4 cities exactly once and return to the starting city. What is the shortest possible route that visits every city?
🧠 What is the memory? (The State)
dp[mask][u] = The shortest distance to visit the set of cities represented by the binary integer mask (e.g. 13 = 1101 in binary means cities 0, 2, and 3 are visited), ending exactly at city u.
🤔 The Core Decision (Plain English)
To find the shortest route ending at city u having visited the set 'mask': Look at all cities v in the visited set (mask). Try traveling from city v to city u, which takes the shortest distance to visit mask excluding u, ending at v (dp[mask\{u}][v]) plus the direct travel cost from v to u.
Labeled Math Equation
🔎 Pattern Signals (When to use it?)
- 🔬Extremely small inputs: The input size N is very small, typically N <= 20 (often 10 to 16).
- 🗺️Subset tracking required: You are traversing nodes or visiting cities (like TSP), and you must track exactly which subset of items has already been visited.
- 🔟NP-hard complexity: The time complexity is exponential (e.g. O(2^N * N^2)), and you use a binary integer (bitmask) as the state key to represent visited/unvisited items.