Why should you care?
Some programming problems look simple but become extremely expensive when solved directly.
A common pattern is:
Solve a problem
↓
Break it into smaller problems
↓
Solve those problems
↓
But the same problems appear again and again
If we calculate the same subproblem repeatedly, we waste time.
Dynamic Programming (DP) solves this problem by remembering solutions to subproblems and reusing them.
Dynamic Programming is one of the most important techniques in algorithmic problem solving.
It appears in:
- Competitive programming
- Interview problems
- Pathfinding
- Scheduling
- Resource allocation
- String algorithms
- Finance
- Bioinformatics
- Game development
- Optimization
The most important idea is simple:
Don't solve the same problem twice.
The Problem
Consider the Fibonacci sequence:
F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2)
For example:
0, 1, 1, 2, 3, 5, 8, 13, 21...
A straightforward recursive implementation is:
static int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
Looks simple.
But look at what happens when calculating:
fibonacci(5)
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \
fib(2) fib(1)
Notice something?
fib(3) is calculated multiple times.
fib(2) is calculated even more times.
For larger n, this repetition becomes enormous.
The recursive solution has approximately:
O(2^n)
time complexity.
We need a way to remember results.
The Concept
Dynamic Programming solves problems by:
- Breaking them into smaller subproblems.
- Solving each subproblem once.
- Storing its result.
- Reusing the stored result whenever needed.
The general idea is:
Original Problem
|
┌────────────┴────────────┐
↓ ↓
Subproblem A Subproblem B
↓ ↓
Solve Solve
↓ ↓
Store Store
└────────────┬────────────┘
↓
Final Answer
Dynamic Programming usually relies on two important properties:
1. Overlapping Subproblems
The same smaller problems appear multiple times.
2. Optimal Substructure
The optimal solution to a problem can be constructed from optimal solutions to its subproblems.
When both properties exist, Dynamic Programming becomes a strong candidate.
Simple Explanation
Imagine you are solving a maze.
Without remembering anything, you might repeatedly walk through the same corridor:
Start
↓
A
↓
B
↓
C
Later, another route reaches B.
Instead of exploring everything from B again, you remember:
"B → destination requires 7 steps."
The next time you reach B:
Look up the answer.
Don't solve it again.
That is the basic idea behind Dynamic Programming.
Real-world Analogy
Imagine you are studying for an exam.
You solve:
Question 1 → Answer: 42
Later, another question requires the answer to Question 1.
Would you solve Question 1 from scratch?
Probably not.
You already know:
Question 1 = 42
So you reuse the answer.
Dynamic Programming does exactly this with subproblems:
Subproblem
↓
Solve once
↓
Remember answer
↓
Reuse whenever needed
Code Example
Let's solve Fibonacci using Dynamic Programming.
Approach 1: Memoization
Memoization is the top-down approach.
We keep the recursive structure but store previously calculated answers.
import java.util.Arrays;
public class Main {
static int fibonacci(int n, int[] dp) {
if (n <= 1) {
return n;
}
// Already calculated
if (dp[n] != -1) {
return dp[n];
}
dp[n] = fibonacci(n - 1, dp)
+ fibonacci(n - 2, dp);
return dp[n];
}
public static void main(String[] args) {
int n = 10;
int[] dp = new int[n + 1];
Arrays.fill(dp, -1);
System.out.println(fibonacci(n, dp));
}
}
Output:
55
Now each Fibonacci value is calculated only once.
Complexity
Before:
Time: O(2^n)
With memoization:
Time: O(n)
Space: O(n)
That is a massive improvement.
Approach 2: Tabulation
Tabulation is the bottom-up approach.
Instead of starting from the final problem and recursively going down, we start with the smallest problems and build upward.
public class Main {
static int fibonacci(int n) {
if (n <= 1) {
return n;
}
int[] dp = new int[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];
}
public static void main(String[] args) {
System.out.println(fibonacci(10));
}
}
The table looks like:
Index: 0 1 2 3 4 5 6 7 8 9 10
Value: 0 1 1 2 3 5 8 13 21 34 55
Each answer is built from previously calculated answers.
Complexity:
Time: O(n)
Space: O(n)
Common Mistakes
Mistake 1: Thinking recursion automatically means Dynamic Programming
Recursion alone is not DP.
This:
f(n) {
return f(n - 1) + f(n - 2);
}
is recursion.
It becomes Dynamic Programming when we identify repeated subproblems and store their results.
Recursion
+
Remember results
=
Memoized Dynamic Programming
Mistake 2: Using DP when subproblems don't overlap
DP is especially useful when the same subproblems are solved repeatedly.
If every subproblem is unique, storing results may provide little or no benefit.
Always ask:
Am I solving the same subproblem multiple times?
Mistake 3: Choosing the wrong state
The DP state represents the information required to describe a subproblem.
For example, in Fibonacci:
dp[i] = Fibonacci number at position i
For a knapsack problem, the state might be:
dp[i][capacity]
For a grid problem:
dp[row][column]
Choosing the correct state is often the hardest part of DP.
Advanced Notes
1. The Four-Step DP Process
A useful way to approach DP problems is:
Step 1 → Define the state
Step 2 → Find the recurrence
Step 3 → Define base cases
Step 4 → Determine the computation order
Let's apply this to Fibonacci.
Step 1: State
dp[i] = Fibonacci(i)
Step 2: Recurrence
dp[i] = dp[i - 1] + dp[i - 2]
Step 3: Base cases
dp[0] = 0
dp[1] = 1
Step 4: Order
Calculate:
dp[2]
dp[3]
dp[4]
...
dp[n]
This four-step process is extremely useful when solving unfamiliar DP problems.
2. Memoization vs Tabulation
| Feature | Memoization | Tabulation |
|---|---|---|
| Direction | Top-down | Bottom-up |
| Usually uses | Recursion | Iteration |
| Calculates | Needed states | Usually all states |
| Stack usage | Yes | No |
| Easy to derive from recursion | Yes | Sometimes |
| Can optimize space | Yes | Yes |
Memoization:
Problem
↓
Recursive subproblem
↓
Recursive subproblem
↓
Store result
Tabulation:
Smallest problem
↓
Next problem
↓
Next problem
↓
Final problem
3. Space Optimization
Our Fibonacci solution stores:
dp[0]
dp[1]
...
dp[n]
But to calculate the next value, we only need the previous two values.
So we can reduce space from:
O(n)
to:
O(1)
public class Main {
static int fibonacci(int n) {
if (n <= 1) {
return n;
}
int prev2 = 0;
int prev1 = 1;
for (int i = 2; i <= n; i++) {
int current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
public static void main(String[] args) {
System.out.println(fibonacci(10));
}
}
Now:
Time: O(n)
Space: O(1)
This is an important DP optimization.
4. 0/1 Knapsack
One of the most famous DP problems is the 0/1 Knapsack.
Suppose you have:
Capacity = 7
Items:
| Item | Weight | Value |
|---|---|---|
| A | 1 | 1 |
| B | 3 | 4 |
| C | 4 | 5 |
| D | 5 | 7 |
Each item can either be:
Take
or:
Don't take
A common DP state is:
dp[i][w]
meaning:
Maximum value using the first
iitems with capacityw.
For each item, we have two choices:
Don't take item
OR
Take item
Therefore:
dp[i][w] =
max(
dp[i-1][w],
value[i] + dp[i-1][w-weight[i]]
)
This is fundamentally different from Fractional Knapsack.
Greedy works for fractional knapsack, but generally fails for 0/1 knapsack.
Dynamic Programming handles the latter.
5. Grid Path Problems
Suppose you have a grid:
S . . .
. . # .
. # . .
. . . E
You can move:
Right
Down
A DP solution can define:
dp[i][j]
as:
Number of ways to reach cell
(i, j).
Then:
dp[i][j] =
dp[i-1][j] + dp[i][j-1]
assuming the cell is not blocked.
This pattern appears in many grid problems.
6. Longest Common Subsequence
DP is also extremely important for strings.
Given:
A = "ABCBDAB"
B = "BDCAB"
We want the longest sequence that appears in both strings without changing the order.
The DP state can be:
dp[i][j]
representing the answer for the first i characters of A and first j characters of B.
If characters match:
dp[i][j] = dp[i-1][j-1] + 1
Otherwise:
dp[i][j] =
max(dp[i-1][j], dp[i][j-1])
This is one of the foundational patterns in string DP.
7. DP on Subsequences
Many DP problems involve choosing or skipping elements.
The recurring structure is:
Take the element
OR
Skip the element
For example:
Element
/ \
Take Skip
This pattern appears in:
- Subset Sum
- 0/1 Knapsack
- Longest Increasing Subsequence
- Partition problems
- Counting subsets
Recognizing this decision structure can make DP problems much easier.
8. DP on Trees
Dynamic Programming is not limited to arrays.
We can also perform DP on trees.
For example:
10
/ \
5 20
/ \
3 7
A DP value can be calculated for each node based on its children.
This is called Tree DP.
The general idea remains the same:
Solve smaller subtrees
↓
Store their results
↓
Build the parent's answer
9. DP on Graphs
DP can also appear in graph problems.
Examples include:
- Shortest paths in DAGs
- Counting paths
- Longest paths in DAGs
- State-based graph problems
For example, in a Directed Acyclic Graph:
A → B → D
\ ↑
→ C ───
We can process vertices in topological order and build answers from previously solved states.
This connects DP with the graph algorithms you have already learned.
10. Dynamic Programming vs Greedy
This distinction is extremely important.
Suppose you need to optimize something.
Greedy asks:
"What is the best choice right now?"
Dynamic Programming asks:
"What is the best result for every relevant state?"
Comparison:
| Greedy | Dynamic Programming |
|---|---|
| Makes a local decision | Evaluates subproblem states |
| Commits to choices | Keeps alternatives through states |
| Usually no backtracking | Stores multiple possibilities |
| Often simpler | Often more memory |
| Requires greedy-choice proof | Uses recurrence/state formulation |
A useful rule:
If you cannot prove that a local choice is safe, consider DP.
11. Dynamic Programming vs Divide and Conquer
You have already learned Merge Sort and Quick Sort.
They use Divide and Conquer:
Divide
↓
Solve independent subproblems
↓
Combine
Dynamic Programming:
Divide
↓
Solve overlapping subproblems
↓
Store results
↓
Reuse results
The key difference is overlap.
If the subproblems are independent, Divide and Conquer is usually appropriate.
If they overlap, Dynamic Programming may be beneficial.
12. Common DP Complexity
If there are:
n states
and each state requires:
O(1)
work:
Time = O(n)
If there are:
n × m states
and each takes constant time:
Time = O(nm)
For example:
LCS → O(nm)
0/1 Knapsack → O(nW)
where W is the capacity.
This is why defining the number of states is important when analyzing DP complexity.
The Bigger Picture
Dynamic Programming is a major step forward in algorithm design.
Your progression now looks like:
Data Structures
↓
Searching
↓
Sorting
↓
DFS / BFS
↓
Greedy Algorithms
↓
Dynamic Programming
The mindset is changing.
Earlier:
How do I store data?
Then:
How do I search efficiently?
Then:
How do I traverse a structure?
Then:
Can I make the best decision immediately?
Now:
What if I need to consider many possible decisions,
but many of those decisions lead to the same subproblems?
That's where Dynamic Programming becomes powerful.
The Most Important Mental Model
Think of Dynamic Programming as:
Solve every important subproblem once, remember the answer, and build the final solution from those answers.
When you encounter a difficult optimization problem, don't immediately think:
"How do I solve the whole problem?"
Instead ask:
"What smaller problem am I really solving?"
Then:
Can I define a state?
↓
Can I express the current answer
using smaller states?
↓
Can I store those answers?
If the answer is yes, you may have found a DP solution.
Summary
Dynamic Programming is a technique for solving problems by breaking them into subproblems and storing their results for reuse.
The key ideas are:
- DP avoids repeated computation.
- It commonly relies on overlapping subproblems.
- It commonly relies on optimal substructure.
- Memoization is the top-down approach.
- Tabulation is the bottom-up approach.
- Choosing the correct DP state is often the hardest part.
- A recurrence describes how states depend on each other.
- Base cases initialize the smallest problems.
- DP can often be optimized for space.
- Classic DP problems include Knapsack, LCS, LIS, Grid Paths, and Subset Sum.
- DP can be applied to arrays, strings, trees, and graphs.
- Greedy commits to a local choice; DP keeps track of multiple possibilities through states.
- Divide and Conquer solves independent subproblems, while DP is especially useful when subproblems overlap.
Top comments (0)