Imagine your teacher asks you to calculate 37 × 48. You work it out and get 1776.
Five minutes later, the teacher asks the same question again.
Would you calculate it again from scratch? Of course not. You would simply remember the answer you already found.
That simple habit, "don't solve the same problem twice", is the heart of Dynamic Programming, or DP.
Dynamic Programming is a technique for solving a problem by breaking it into smaller overlapping subproblems, solving each subproblem only once, and storing its result so it can be reused.
DP is one of the most important topics for coding interviews and competitive programming. Many problems that look impossible with brute force become fast and clean once you see the DP structure.
In this chapter, we will build the idea from the ground up. The next chapters then apply it to 1D problems, 2D problems, knapsack problems, and string problems.
The Problem with Plain Recursion
In the Recursion chapter, we wrote a recursive Fibonacci function. Here it is again, renamed to fib and returning a long so that bigger values fit:
static long fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}It is short and correct. But it is also very slow.
Let's draw the recursion tree for fib(5):
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)Look carefully. The same calls appear again and again:
fib(3) is calculated 2 times
fib(2) is calculated 3 times
fib(1) is calculated 5 times
fib(0) is calculated 3 timesEven for a tiny input like 5, the function makes 15 calls to compute just 6 different values (fib(0) to fib(5)).
For fib(30), it makes 2,692,537 calls, even though there are only 31 different values to compute. The time complexity is exponential, roughly O(2ⁿ).
All this waste comes from one thing: the same subproblem is solved again and again.
The Key Idea: Remember Answers
What if, the first time we compute fib(3), we write the answer down somewhere?
memo[3] = 2The next time someone asks for fib(3), we just look it up instead of recomputing it.
With that one change, every value from fib(0) to fib(n) is computed only once. The exponential tree collapses into a simple chain:
fib(5) → fib(4) → fib(3) → fib(2) → fib(1)
↘ fib(0)
(every other call is an instant lookup)The time complexity drops from O(2ⁿ) to O(n).
That is Dynamic Programming in one sentence:
DP = Recursion + Remembering results (so no subproblem is solved twice).
When Can We Use Dynamic Programming?
DP does not work on every problem. A problem is a good fit for DP when it has two properties.
1. Overlapping Subproblems
The problem can be broken into smaller subproblems, and the same subproblems appear many times.
Fibonacci is a perfect example: fib(3) is needed by both fib(5) and fib(4).
Compare this with Merge Sort. Merge sort also splits the problem into smaller parts, but each half of the array is different. No subproblem repeats, so there is nothing to remember. That is why merge sort is Divide and Conquer, not DP.
2. Optimal Substructure
The best answer to the big problem can be built from the best answers to its subproblems.
For example, think about the shortest route from city A to city C that passes through city B:
A ───── B ───── CIf the route A → B → C is the shortest, then its A → B part must also be the shortest way from A to B. Otherwise, we could replace that part with a shorter one and get an even shorter total route.
So the optimal solution contains optimal solutions to smaller problems.
Overlapping subproblems + Optimal substructure → Dynamic Programming is a good choice.
Two Ways to Write DP
There are two standard styles of writing a DP solution:
Dynamic Programming
├── Top-Down (Memoization)
└── Bottom-Up (Tabulation)Both compute the same values. They just compute them in a different order.
Top-Down DP: Memoization
Memoization means: write the normal recursive solution, then add a cache (usually an array or a HashMap) to store results.
The steps are:
1. Before computing, check the cache.
2. If the answer is already there, return it.
3. Otherwise, compute it recursively.
4. Store the answer in the cache before returning.Here is Fibonacci with memoization:
static long fibMemo(int n, long[] memo) {
if (n <= 1) {
return n;
}
if (memo[n] != -1) {
return memo[n]; // already solved
}
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}We fill the memo array with -1 first, which means "not computed yet":
long[] memo = new long[n + 1];
Arrays.fill(memo, -1);Why -1 and not 0? Because 0 can be a real answer (fib(0) = 0). We need a value that can never be a real answer, so we can tell "not computed" apart from "computed and equal to 0".
Memoization is called top-down because we start from the big problem (fib(n)) and go down to smaller ones as needed.
Bottom-Up DP: Tabulation
Tabulation removes recursion completely. We create a table and fill it from the smallest subproblem up to the biggest one.
For Fibonacci:
dp[i] = the i-th Fibonacci number
dp[0] = 0
dp[1] = 1
dp[i] = dp[i - 1] + dp[i - 2]We fill the table from left to right:
index : 0 1 2 3 4 5 6
dp : 0 1 1 2 3 5 8
↑
dp[2] = dp[1] + dp[0]When we compute dp[i], the values dp[i - 1] and dp[i - 2] are already in the table, so we never wait for anything.
static long fibTab(int n) {
if (n <= 1) {
return n;
}
long[] dp = new long[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}This is called bottom-up because we start from the base cases at the bottom and build up to the answer.
Space Optimization
Look at the tabulation loop again. To compute dp[i], we only need the previous two values. Everything older is never used again.
So instead of a full array, two variables are enough:
static long fibOptimized(int n) {
if (n <= 1) {
return n;
}
long prev2 = 0; // fib(i - 2)
long prev1 = 1; // fib(i - 1)
for (int i = 2; i <= n; i++) {
long current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}Time stays O(n), but extra space drops from O(n) to O(1).
This is a very common final step in DP: first write the table, then notice which rows or cells you actually need.
Complete Example: All Four Versions
Let's put everything together and count how many function calls each recursive version makes.
import java.util.Arrays;
class Main {
static long calls = 0;
// 1. Plain recursion
static long fibRecursive(int n) {
calls++;
if (n <= 1) {
return n;
}
return fibRecursive(n - 1) + fibRecursive(n - 2);
}
// 2. Memoization (top-down)
static long fibMemo(int n, long[] memo) {
calls++;
if (n <= 1) {
return n;
}
if (memo[n] != -1) {
return memo[n];
}
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
// 3. Tabulation (bottom-up)
static long fibTab(int n) {
if (n <= 1) {
return n;
}
long[] dp = new long[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// 4. Space optimized
static long fibOptimized(int n) {
if (n <= 1) {
return n;
}
long prev2 = 0;
long prev1 = 1;
for (int i = 2; i <= n; i++) {
long current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
public static void main(String[] args) {
int n = 30;
calls = 0;
System.out.println("Recursive : " + fibRecursive(n) + " (calls = " + calls + ")");
long[] memo = new long[n + 1];
Arrays.fill(memo, -1);
calls = 0;
System.out.println("Memoized : " + fibMemo(n, memo) + " (calls = " + calls + ")");
System.out.println("Tabulated : " + fibTab(n));
System.out.println("Optimized : " + fibOptimized(n));
System.out.println("fib(50) = " + fibOptimized(50));
System.out.println("fib(90) = " + fibOptimized(90));
}
}Output:
Recursive : 832040 (calls = 2692537)
Memoized : 832040 (calls = 59)
Tabulated : 832040
Optimized : 832040
fib(50) = 12586269025
fib(90) = 2880067194370816120Same answer, but 2,692,537 calls versus 59 calls. That is the power of DP.
Try running fibRecursive(50) yourself. It makes tens of billions of calls and takes a very long time, while the DP versions answer instantly.
Memoization vs Tabulation
Memoization (Top-Down) | Tabulation (Bottom-Up) |
|---|---|
Recursive | Iterative (loops) |
Starts from the main problem | Starts from the base cases |
Computes only the subproblems that are actually needed | Usually computes every subproblem in the table |
Easy to write if you already have the recursive solution | You must figure out the correct filling order |
Uses the call stack, so very deep recursion can cause | No recursion, no stack overflow risk |
Slight overhead of function calls | Usually a little faster in practice |
Harder to space-optimize | Easy to space-optimize (keep only needed rows) |
Both have the same Big O time complexity for the same recurrence. A good strategy in interviews is:
1. Write the brute-force recursion.
2. Add memoization.
3. Convert to tabulation.
4. Optimize space if possible.Interviewers love to see this progression because it shows you understand why the solution works.
How to Solve Any DP Problem
Most DP problems can be solved with the same five questions.
Step 1: Define the State
What does dp[i] (or dp[i][j]) mean? Write it in plain English.
dp[i] = the i-th Fibonacci numberThis is the most important step. If the meaning of the state is fuzzy, everything after it will be confusing.
Step 2: Find the Recurrence (Transition)
How can dp[i] be built from smaller states?
dp[i] = dp[i - 1] + dp[i - 2]A helpful trick: think about the last choice you make. For Fibonacci-style problems like climbing stairs, the last step was either 1 stair or 2 stairs, which leads directly to the recurrence.
Step 3: Set the Base Cases
What are the smallest problems whose answers you know directly?
dp[0] = 0
dp[1] = 1Step 4: Decide the Order of Computation
In tabulation, every state must be computed after the states it depends on. Since dp[i] depends on smaller indices, we loop from small to large.
Step 5: Identify the Final Answer
Which cell holds the answer? Here, it is dp[n]. In other problems, it might be the maximum over the whole table, or the last cell of a grid.
State → Recurrence → Base cases → Order → Answer.
Time and Space Complexity of DP
There is a simple formula that works for most DP solutions:
Time = (number of states) × (work per state)
Space = (number of states) [before optimization]For Fibonacci:
States → n + 1 (dp[0] ... dp[n])
Work per state → O(1) (one addition)
Time → O(n)
Space → O(n), or O(1) after optimizationIn later chapters, you will see states like dp[i][j]. If i goes up to n and j goes up to m, there are n × m states, and the time is usually O(n × m).
DP vs Divide and Conquer vs Greedy
You have already seen Divide and Conquer and Greedy Algorithms. All three break problems into smaller pieces, so it's easy to mix them up.
Technique | Key Idea | Subproblems | Example |
|---|---|---|---|
Divide and Conquer | Split, solve independently, combine | Independent (do not repeat) | Merge Sort, Binary Search |
Greedy | Take the best-looking choice at each step, never look back | Only one path is followed | Activity selection, Dijkstra |
Dynamic Programming | Try all choices, but reuse stored results | Overlapping (repeat many times) | Fibonacci, Knapsack, LCS |
Remember the coin example from the Greedy Algorithms chapter? It shows exactly why DP is sometimes needed instead of greedy.
Coins: {1, 3, 4}. Make the amount 6 using the fewest coins.
Greedy (always take the biggest coin that fits):
6 → take 4 → 2 left → take 1 → 1 left → take 1
Result: 4 + 1 + 1 = 3 coins
Best answer:
3 + 3 = 2 coinsGreedy picked the coin that looked best right now, and it was wrong. DP considers every choice (using 1, 3, or 4 as the last coin) and picks the best, so it always finds 2. We'll write this solution in the next chapter.
Common Mistakes
1. Using 0 as "not computed"
If 0 can be a valid answer, the memo check if (memo[n] != 0) fails, and you silently lose all the speed-up. Use -1, a Long/Integer array with null, or a separate boolean[] array.
2. Forgetting to store the result
// Wrong: computes but never saves
return fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
// Correct
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];Without the assignment, the code is still exponential.
3. Wrong filling order in tabulation
If dp[i] depends on dp[i - 1], you must compute dp[i - 1] first. Filling in the wrong order reads values that are still 0.
4. Integer overflow
DP answers often grow very fast. Fibonacci numbers overflow an int at fib(47) and a long at fib(93). Use long, and if the problem says "return the answer modulo 10⁹ + 7", apply % MOD after every addition.
5. Unclear state definition
If you can't say in one sentence what dp[i] means, stop and define it before writing code. Most DP bugs come from a vague state.
6. Using DP when there is no overlap
If subproblems never repeat (like in merge sort), memoization just adds memory use without any speed-up.
How to Recognize a DP Problem
These phrases in a problem statement are strong hints that DP might be needed:
"Find the minimum / maximum ..." (cost, profit, length)
"Count the number of ways to ..."
"Is it possible to ..." (reach a target, partition, form a string)
"Longest / shortest ... subsequence"
You have to make a sequence of choices, and each choice affects future choices
A brute-force recursive solution exists but is exponential
A good habit: when you write a recursive solution, ask yourself "Can the same function call happen twice with the same arguments?" If yes, DP will help.
What's Coming Next
Now that you know the core idea, the next chapters apply it to the most common families of DP problems:
Dynamic Programming
├── 1D DP → climbing stairs, house robber, coin change, LIS
├── 2D DP → grid paths, minimum path sum, triangle
├── Knapsack → 0/1 knapsack, subset sum, unbounded knapsack
└── DP on Strings → LCS, edit distance, palindromic subsequenceThe Main Idea
Dynamic Programming is a way of solving problems that have overlapping subproblems and optimal substructure by solving each subproblem once and storing its result.
There are two styles:
Memoization → Top-down, recursion + cache
Tabulation → Bottom-up, loops + tableEvery DP solution comes from the same five steps:
1. Define the state
2. Write the recurrence
3. Set the base cases
4. Choose the computation order
5. Return the right cellAnd its cost is usually:
Time = number of states × work per stateIf your recursive solution keeps solving the same subproblem again and again, store the answer. That single idea turns many exponential solutions into polynomial ones.