Dynamic Programming (DP)
Dynamic Programming (DP) is one of the most important problem-solving techniques in DSA.
It is mainly used when a problem can be broken into smaller subproblems, and the same subproblems are solved again and again.
The key idea is:
Solve each subproblem once, store its answer, and reuse it whenever needed.
1. Why Do We Need Dynamic Programming?
Let's start with a simple example: Fibonacci numbers.
The Fibonacci sequence is:
0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Formula:
F(n) = F(n-1) + F(n-2)
A simple recursive implementation:
int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); }
Suppose we calculate:
fib(5)
The recursion looks like:
fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1) / \ fib(2) fib(1)
Notice something important:
fib(3)
is calculated multiple times.
And:
fib(2)
is also calculated multiple times.
This is repeated work.
Dynamic Programming eliminates this repeated work.
2. The Core Idea of DP
Without DP:
Calculate ↓ Calculate same thing again ↓ Calculate same thing again ↓ Waste time
With DP:
Calculate subproblem ↓ Store answer ↓ Need it again? ↓ Use stored answer
So:
DP = Recursion/Iteration + Storing Results
But this is a simplified mental model. DP specifically applies when the problem has the right structure, especially overlapping subproblems and optimal substructure.
3. Two Important Properties of DP
Before deciding whether a problem can use DP, look for two properties.
1. Overlapping Subproblems
The same smaller problem appears multiple times.
Example:
F(5) ├── F(4) │ ├── F(3) │ └── F(2) │ └── F(3) ├── F(2) └── F(1)
F(3) and F(2) are repeated.
This is:
Overlapping Subproblems
2. Optimal Substructure
The optimal answer to a larger problem can be constructed from optimal answers to its smaller subproblems.
For example, in some shortest-path and knapsack problems:
Optimal big solution ↓ Optimal smaller solutions
This property is essential for many optimization DP problems.
4. DP vs Divide and Conquer
You just studied Divide and Conquer.
They look similar, but there is an important difference.
Divide and Conquer
Subproblems are generally independent.
Problem / \ A B
You solve A and B separately.
Examples:
- Merge Sort
- Quick Sort
- Binary Search
Dynamic Programming
Subproblems often overlap.
Problem / \ A B \ / C
Both A and B may need the answer to C.
Instead of calculating C twice:
Calculate C ↓ Store C ↓ Reuse C
That's the major difference.
5. The Two Approaches to DP
There are two main ways to implement Dynamic Programming:
- Top-Down DP
- Bottom-Up DP
6. Top-Down DP — Memoization
Top-down means:
Start with the original problem and recursively break it down.
Then store the answers of subproblems.
This technique is called Memoization.
Example: Fibonacci
Normal recursion:
int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); }
Now add a DP array.
int fib(int n, vector<int>& dp) { if (n <= 1) return n; if (dp[n] != -1) return dp[n]; dp[n] = fib(n - 1, dp) + fib(n - 2, dp); return dp[n]; }
Usage:
int n = 10; vector<int> dp(n + 1, -1); cout << fib(n, dp);
7. How Memoization Works
Suppose:
fib(5)
First time:
fib(5) ↓ fib(4) ↓ fib(3) ↓ ...
Results are stored:
dp[0] = 0 dp[1] = 1 dp[2] = 1 dp[3] = 2 dp[4] = 3 dp[5] = 5
If later we need:
fib(3)
we don't calculate it again.
We simply do:
if (dp[3] != -1) return dp[3];
8. Bottom-Up DP — Tabulation
Bottom-up works in the opposite direction.
Instead of starting with the final problem, we start with the smallest subproblems.
This is called Tabulation.
For Fibonacci:
F(0) = 0 F(1) = 1 F(2) = F(1) + F(0) F(3) = F(2) + F(1) F(4) = F(3) + F(2) ...
C++:
int fib(int n) { if (n <= 1) return n; vector<int> dp(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]; }
9. Memoization vs Tabulation
| Feature | Memoization | Tabulation |
|---|---|---|
| Direction | Top → Down | Bottom → Up |
| Technique | Recursion | Iteration |
| Uses call stack | Yes | No |
| Stores results | Yes | Yes |
| Usually easier to derive | Yes | Sometimes |
| Risk of recursion depth | Yes | No |
| Can avoid unused states | Often | Usually computes planned states |
Easy memory trick:
Memoization = Recursion + Cache Tabulation = Table + Loop
10. The Most Important DP Question
When you see a DP problem, don't immediately write code.
First ask:
What does
dp[i]mean?
This is called defining the DP state.
For example:
dp[i] = Fibonacci number at position i
or:
dp[i] = minimum cost to reach position i
or:
dp[i] = maximum profit using first i items
A good state definition makes the rest of the solution much easier.
11. Four Main Steps to Solve DP Problems
A very useful process is:
1. Define the state ↓ 2. Find the recurrence/transition ↓ 3. Define base cases ↓ 4. Decide computation order
Let's understand each.
12. Step 1 — Define the State
Suppose:
You can climb either 1 or 2 stairs at a time. How many ways can you reach stair
n?
Define:
dp[i] = number of ways to reach stair i
That's our state.
13. Step 2 — Find the Transition
To reach stair i, the previous step could have been:
i - 1
or:
i - 2
Therefore:
dp[i] = dp[i-1] + dp[i-2]
This is the transition or recurrence relation.
14. Step 3 — Base Cases
What happens at the beginning?
dp[0] = 1 dp[1] = 1
Why dp[0] = 1?
There is one way to be at the starting position: do nothing.
Then:
dp[2] = dp[1] + dp[0] = 1 + 1 = 2
The two ways are:
1 + 1 2
15. Step 4 — Compute the Answer
int climbStairs(int n) { vector<int> dp(n + 1); dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }
Complexity:
Time: O(n)
Space: O(n)
16. Space Optimization
Notice something:
dp[i] = dp[i-1] + dp[i-2]
We don't need the entire array.
We only need the previous two values.
So:
int climbStairs(int n) { if (n <= 1) return 1; int prev2 = 1; int prev1 = 1; for (int i = 2; i <= n; i++) { int current = prev1 + prev2; prev2 = prev1; prev1 = current; } return prev1; }
Now:
Time: O(n)
Space: O(1)
This technique is called Space Optimization.
17. The Classic 0/1 Knapsack Problem
One of the most important DP problems is 0/1 Knapsack.
Suppose you have:
Items: Weight Value 2 3 3 4 4 5 5 8
Bag capacity:
5
You want to maximize the total value.
Each item can either be:
Take it OR Don't take it
That's why it's called 0/1.
0 = don't take 1 = take
18. Why Greedy Doesn't Always Work
You learned Greedy before.
For 0/1 Knapsack, simple greedy strategies aren't generally guaranteed to give the optimal answer.
Why?
Because an item with the best value/weight ratio may prevent a better combination.
So we consider choices systematically using DP.
19. Knapsack DP State
Define:
dp[i][w]
as:
Maximum value we can obtain using the first
iitems with capacityw.
Now we have two choices.
Don't take item
dp[i][w] = dp[i-1][w]
Take item
If its weight fits:
dp[i][w] = value[i-1] + dp[i-1][w-weight[i-1]]
Therefore:
dp[i][w] = max( dp[i-1][w], value[i-1] + dp[i-1][w-weight[i-1]] )
20. 0/1 Knapsack C++ Code
int knapsack( vector<int>& weight, vector<int>& value, int capacity ) { int n = weight.size(); vector<vector<int>> dp( n + 1, vector<int>(capacity + 1, 0) ); for (int i = 1; i <= n; i++) { for (int w = 0; w <= capacity; w++) { // Don't take item dp[i][w] = dp[i - 1][w]; // Take item if possible if (weight[i - 1] <= w) { dp[i][w] = max( dp[i][w], value[i - 1] + dp[i - 1][w - weight[i - 1]] ); } } } return dp[n][capacity]; }
Complexity:
Time = O(n × capacity) Space = O(n × capacity)
21. Another Classic: Coin Change
Suppose coins are:
1, 2, 5
Target:
11
Find the minimum number of coins.
One solution:
5 + 5 + 1
Answer:
3
DP State
Define:
dp[x] = minimum coins required to make amount x
Transition:
dp[x] = min( dp[x - coin] + 1 )
for every coin that can be used.
C++ Code
int coinChange(vector<int>& coins, int amount) { const int INF = amount + 1; vector<int> dp(amount + 1, INF); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int coin : coins) { if (coin <= i) { dp[i] = min( dp[i], dp[i - coin] + 1 ); } } } if (dp[amount] == INF) return -1; return dp[amount]; }
Complexity:
Time = O(amount × number_of_coins) Space = O(amount)
22. 0/1 Knapsack vs Unbounded Knapsack
This is an important distinction.
0/1 Knapsack
Each item can be used once.
Item → Take / Don't Take
Unbounded Knapsack
An item can be used multiple times.
Item → Can take again
Coin Change is generally an example of an unbounded setting because the same coin denomination can be used repeatedly.
23. Longest Common Subsequence (LCS)
Another extremely important DP problem is LCS.
Suppose:
A = "abcde" B = "ace"
The longest common subsequence is:
"ace"
Notice:
a b c d e | | | a c e
The characters don't have to be adjacent.
24. LCS DP State
Define:
dp[i][j]
as:
LCS length between the first
icharacters of A and the firstjcharacters of B.
Now compare the last characters.
If they match:
A[i-1] == B[j-1]
then:
dp[i][j] = 1 + dp[i-1][j-1]
If they don't match:
dp[i][j] = max( dp[i-1][j], dp[i][j-1] )
25. LCS C++ Code
int lcs(string a, string b) { int n = a.size(); int m = b.size(); vector<vector<int>> dp( n + 1, vector<int>(m + 1, 0) ); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (a[i - 1] == b[j - 1]) { dp[i][j] = 1 + dp[i - 1][j - 1]; } else { dp[i][j] = max( dp[i - 1][j], dp[i][j - 1] ); } } } return dp[n][m]; }
Complexity:
Time = O(n × m) Space = O(n × m)
26. LCS vs Longest Common Substring
Don't confuse these.
Subsequence
Characters don't need to be continuous.
"abcde" "ace" LCS = "ace"
Substring
Characters must be continuous.
"abcdef" "zcdxy" Common substring = "cd"
This distinction appears frequently in interviews and competitive programming.
27. Fibonacci: A Complete DP Evolution
It's useful to see how a problem evolves.
Version 1 — Normal recursion
int fib(int n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); }
Time:
O(2^n)
Version 2 — Memoization
int fib(int n, vector<int>& dp) { if (n <= 1) return n; if (dp[n] != -1) return dp[n]; return dp[n] = fib(n-1, dp) + fib(n-2, dp); }
Time:
O(n)
Space:
O(n)
Version 3 — Tabulation
int fib(int n) { vector<int> dp(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]; }
Time:
O(n)
Space:
O(n)
Version 4 — Space Optimized
int fib(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; }
Time:
O(n)
Space:
O(1)
This is an excellent example of how DP can transform an inefficient recursive solution into an efficient one.
28. DP State Patterns
Most DP problems can be recognized by their state structure.
1D DP
dp[i]
Examples:
- Fibonacci
- Climbing Stairs
- House Robber
- Minimum Cost Climbing Stairs
2D DP
dp[i][j]
Examples:
- LCS
- Edit Distance
- 0/1 Knapsack
- Grid paths
3D DP
dp[i][j][k]
Used when three changing parameters are necessary.
For example:
position remaining capacity number of selected items
29. Common DP Categories
You will encounter many patterns.
1. Linear DP
dp[i]
Examples:
- Fibonacci
- Climbing Stairs
- House Robber
2. Grid DP
dp[i][j]
Examples:
- Unique Paths
- Minimum Path Sum
3. Knapsack DP
Examples:
- 0/1 Knapsack
- Unbounded Knapsack
- Subset Sum
- Partition Equal Subset Sum
4. String DP
Examples:
- LCS
- Longest Palindromic Subsequence
- Edit Distance
5. Interval DP
State represents an interval:
dp[l][r]
Examples:
- Matrix Chain Multiplication
- Burst Balloons
- Palindrome partitioning variants
6. Tree DP
DP is performed on tree nodes.
Examples:
- Maximum independent set on a tree
- Tree diameter variants
- Maximum path problems
7. Bitmask DP
Uses bits to represent states.
Example:
dp[mask][i]
Common in subset/permutation problems.
8. Digit DP
Used for counting numbers satisfying digit-related constraints.
9. DP on DAGs
Use graph structure and topological ordering.
30. DP on a Grid
Consider:
1 2 3 4 5 6 7 8 9
Suppose you start at the top-left and can move:
Right → Down ↓
How many ways can you reach the bottom-right?
Define:
dp[i][j] = number of ways to reach cell (i,j)
To reach (i,j), you can come from:
(i-1,j)
or:
(i,j-1)
Therefore:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
This is a very common DP pattern.
31. House Robber Example
Suppose houses contain:
[2, 7, 9, 3, 1]
You cannot rob two adjacent houses.
You want maximum money.
At every house you have two choices:
Don't rob current house OR Rob current house
Define:
dp[i] = maximum money from first i houses
Transition:
dp[i] = max( dp[i-1], dp[i-2] + money[i] )
Why?
If you rob house i, you cannot rob the previous one.
C++:
int rob(vector<int>& money) { int n = money.size(); if (n == 0) return 0; if (n == 1) return money[0]; vector<int> dp(n); dp[0] = money[0]; dp[1] = max(money[0], money[1]); for (int i = 2; i < n; i++) { dp[i] = max( dp[i - 1], dp[i - 2] + money[i] ); } return dp[n - 1]; }
Complexity:
Time = O(n) Space = O(n)
This can also be optimized to O(1) space.
32. DP and State Transition
A useful way to think about DP is:
STATE ↓ What information describes the current problem? ↓ CHOICES ↓ What decisions can I make? ↓ TRANSITION ↓ How does each choice change the state? ↓ BASE CASE ↓ What happens at the smallest state?
For example, House Robber:
State: dp[i] Choices: Take house Don't take house Transition: max( don't take, take + dp[i-2] ) Base: dp[0], dp[1]
33. How to Recognize a DP Problem
Look for these signals:
Signal 1: "Maximum"
Maximum profit Maximum value Maximum length
Signal 2: "Minimum"
Minimum cost Minimum number of operations Minimum coins
Signal 3: "Number of ways"
How many ways? How many possible paths? How many combinations?
Signal 4: Choices
Take / Don't take Choose A / Choose B Move right / Move down Buy / Sell
Signal 5: Repeated subproblems
If recursion keeps solving the same state again, DP may help.
34. A General DP Template
Memoization
int solve(int state) { if (base_case) return base_value; if (dp[state] != -1) return dp[state]; dp[state] = ...; return dp[state]; }
Tabulation
vector<int> dp(n + 1); initialize base cases; for (int state = smallest; state <= largest; state++) { dp[state] = transition; } return dp[n];
For 2D:
vector<vector<int>> dp( n + 1, vector<int>(m + 1) ); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[i][j] = transition; } }
35. DP Complexity
A powerful rule:
DP complexity is often approximately: number of states × transitions per state.
Example:
Fibonacci
States:
n
Transitions per state:
constant
Therefore:
O(n)
Knapsack
States:
n × capacity
Transitions:
constant
Therefore:
O(n × capacity)
LCS
States:
n × m
Transitions:
constant
Therefore:
O(n × m)
This way of thinking is very useful in DP.
36. DP vs Backtracking
You studied Backtracking earlier.
Backtracking
Try choice ↓ Explore ↓ Undo ↓ Try another choice
It may explore many possibilities.
DP
Solve state ↓ Store result ↓ Reuse result
The key difference is that DP reuses overlapping subproblems, while backtracking typically explores a decision tree.
Sometimes a backtracking problem can be converted into DP if many different paths reach the same state.
37. DP vs Greedy
Greedy
Makes the best local decision:
Best now ↓ Commit ↓ Continue
DP
Considers possible choices and stores the best result for each state:
Choice A ──┐ ├── Best result Choice B ──┘
Greedy is generally faster/simpler when it is provably correct.
DP is useful when local choices aren't sufficient and subproblem reuse exists.
38. DP vs Divide and Conquer
The easiest comparison:
Divide & Conquer ↓ Independent subproblems ↓ Solve separately ↓ Combine
Dynamic Programming ↓ Overlapping subproblems ↓ Solve once ↓ Store ↓ Reuse
39. Common DP Problems You Should Know
For interviews and DSA practice, these are especially important:
Beginner
- Fibonacci
- Climbing Stairs
- Min Cost Climbing Stairs
- House Robber
- Maximum Subarray
Intermediate
- Coin Change
- 0/1 Knapsack
- Subset Sum
- Partition Equal Subset Sum
- Unique Paths
- Minimum Path Sum
- Longest Increasing Subsequence
- Longest Common Subsequence
Advanced
- Edit Distance
- Matrix Chain Multiplication
- Longest Palindromic Subsequence
- Interval DP
- Tree DP
- Bitmask DP
- Digit DP
- DP on DAGs
40. The Most Important DP Skill
Don't memorize 20 different formulas.
Instead, learn to derive them.
When you see a problem, ask:
1. What is my state? ↓ 2. What choices do I have? ↓ 3. What happens after each choice? ↓ 4. Can I express the answer using smaller states? ↓ 5. What are the base cases? ↓ 6. How many states exist? ↓ 7. How many transitions per state?
This is the real skill behind DP.
41. A Practical DP Example
Suppose:
You have stairs
n. You can climb either 1 or 2 steps. Find the number of ways to reach the top.
Step 1 — State
dp[i] = number of ways to reach stair i
Step 2 — Choices
1 step 2 steps
Step 3 — Transition
dp[i] = dp[i-1] + dp[i-2]
Step 4 — Base cases
dp[0] = 1 dp[1] = 1
Step 5 — Complexity
States:
n
Work per state:
O(1)
Therefore:
Time = O(n) Space = O(n)
Step 6 — Optimize
Only previous two states are required:
Space = O(1)
This six-step process is exactly how you should approach many DP problems.
42. DP Mental Model
Keep this picture in your mind:
BIG PROBLEM │ ↓ Smaller States / | \ / | \ State A State B State C │ │ │ └───────┼───────┘ ↓ Store Answers ↓ Reuse Answers ↓ FINAL ANSWER
Or even simpler:
DP Problem ↓ Break into states ↓ Find recurrence ↓ Solve each state once ↓ Store ↓ Reuse ↓ Answer
Final Summary
Dynamic Programming = solving overlapping subproblems efficiently by storing their results.
The two most important properties are:
1. Overlapping Subproblems 2. Optimal Substructure
The two main approaches are:
Memoization = Top-Down = Recursion + Cache
Tabulation = Bottom-Up = Table + Iteration
The most important DP concepts are:
- State → What does
dp[i]ordp[i][j]represent? - Transition → How do we calculate the current state?
- Base Case → What are the smallest states?
- Computation Order → In what order should states be calculated?
- Space Optimization → Do we need the entire DP table?
- State count × transitions → Often determines complexity.
Important examples
| Problem | Typical DP |
|---|---|
| Fibonacci | dp[i] |
| Climbing Stairs | dp[i] |
| House Robber | dp[i] |
| Coin Change | dp[amount] |
| 0/1 Knapsack | dp[i][capacity] |
| LCS | dp[i][j] |
| Grid Paths | dp[i][j] |
| Edit Distance | dp[i][j] |
| LIS | dp[i] / optimized variants |
The one rule to remember
Don't start by asking "Which DP formula should I memorize?" Start by asking "What is the state, what choices do I have, and how can I derive the current answer from smaller states?"