Dynamic Programming
Dynamic Programming
Dynamic Programming (DP) is an important problem-solving strategy in algorithmic thinking. It is mainly used when a problem can be divided into smaller sub-problems, and the same sub-problems occur repeatedly.
The central idea is:
Solve each sub-problem only once, store its result, and reuse it whenever needed.
A simple way to remember DP is:
DP = Divide the problem + Solve the subproblem + Remember the answers
1. Why Do We Need Dynamic Programming?
Consider the Fibonacci sequence:
The Fibonacci numbers are defined as:
For example:
A straightforward recursive solution repeatedly calculates the same values.
F(5) / \ F(4) F(3) / \ / \ F(3) F(2) F(2) F(1) / \ F(2) F(1)
Notice that F(3) and F(2) are calculated multiple times.
This is repeated work.
Dynamic programming solves this problem by saying:
"If I have already calculated F(3), why calculate it again? I will store the answer."
2. Two Important Properties of DP
A problem is generally suitable for dynamic programming when it has two important properties:
- Overlapping Sub-problems
- Optimal Substructure
Let's understand both.
3. Overlapping Sub-Problems
Meaning
A problem has overlapping sub-problems when the same smaller problems occur repeatedly while solving the larger problem.
Consider Fibonacci:
F(5) ├── F(4) │ ├── F(3) │ └── F(2) │ └── F(3) ├── F(2) └── F(1)
Here:
F(3)
appears more than once.
Similarly:
F(2)
also appears multiple times.
Instead of calculating them repeatedly, DP stores their answers.
F(2) = 1 F(3) = 2 F(4) = 3 F(5) = 5
Simple definition
Overlapping sub-problems means that the same smaller problems are encountered multiple times.
4. Optimal Substructure
This is particularly important in optimization problems.
A problem has optimal substructure when:
An optimal solution to the larger problem can be constructed from optimal solutions to its smaller sub-problems.
Suppose we want to travel:
Thiruvananthapuram → Ernakulam
and the optimal route passes through Alappuzha.
Thiruvananthapuram ↓ Alappuzha ↓ Ernakulam
Suppose the shortest route from Thiruvananthapuram to Ernakulam is:
Thiruvananthapuram ↓ Alappuzha ↓ Ernakulam
Then the portion:
Thiruvananthapuram → Alappuzha
must itself be the shortest route between those two cities.
Similarly:
Alappuzha → Ernakulam
must also be the shortest route between those cities.
Otherwise, if we could find a shorter route between either pair, we could replace that portion and obtain a shorter overall route—which would contradict the claim that the original route was optimal.
Simple definition
Optimal substructure means that an optimal solution can be constructed from optimal solutions to its sub-problems.
5. Bellman's Principle of Optimality
The idea above is known as the Principle of Optimality, associated with Richard Bellman.
In simple terms:
An optimal solution contains optimal solutions to its sub-problems.
For a shortest-route problem:
Optimal route ↓ ┌───┴────┐ ↓ ↓ Optimal Optimal part part
This principle is fundamental to many dynamic programming algorithms.
6. The Main Idea of Dynamic Programming
Suppose a large problem can be represented as:
Large Problem ↓ Smaller Problems ↓ Solve them ↓ Store answers ↓ Reuse answers ↓ Final Solution
Therefore:
PROBLEM ↓ Divide into sub-problems ↓ Are sub-problems repeated? ↓ YES ↓ Solve sub-problem once ↓ STORE ↓ REUSE ↓ Solve larger problem
7. Dynamic Programming vs Ordinary Recursion
Consider Fibonacci.
Ordinary recursion
fib(5) ├── fib(4) │ ├── fib(3) │ └── fib(2) │ └── fib(3) ├── fib(2) └── fib(1)
The same values are calculated repeatedly.
DP
Calculate fib(2) → Store Calculate fib(3) → Store Calculate fib(4) → Store Calculate fib(5) → Store
Each sub-problem is solved once.
8. The Two Approaches to Dynamic Programming
Dynamic programming can mainly be implemented in two ways:
1. Memoization – Top Down
2. Tabulation – Bottom Up
9. Memoization – Top-Down Approach
Memoization uses recursion but stores the answers of already solved sub-problems.
The basic idea is:
Need answer? ↓ Already stored? ↙ ↘ YES NO ↓ ↓ Return Calculate answer ↓ Store ↓ Return
Example
def fib(n, memo): if n in memo: return memo[n] if n <= 1: return n memo[n] = fib(n-1, memo) + fib(n-2, memo) return memo[n] memo = {} print(fib(8, memo))
The important line is:
if n in memo: return memo[n]
It means:
"If I have already calculated this value, don't calculate it again."
10. Why Is It Called Top-Down?
We start with the large problem:
fib(8)
and recursively move downward:
fib(8) ↓ fib(7), fib(6) ↓ smaller problems ↓ base cases
Then we store the answers as we return.
Therefore:
Top-down = Start with the original problem and recursively move toward smaller problems.
11. Tabulation – Bottom-Up Approach
Tabulation takes the opposite approach.
Instead of starting with the large problem, we start with the smallest problems and gradually build the solution.
For Fibonacci:
F(0) = 0 F(1) = 1
Then:
F(2) = F(1) + F(0) = 1 F(3) = F(2) + F(1) = 2 F(4) = F(3) + F(2) = 3 F(5) = F(4) + F(3) = 5
We can store them in a table:
n | F(n) |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
| 6 | 8 |
Python:
def fib(n): dp = [0] * (n + 1) if n >= 1: dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n] print(fib(6))
12. Why Is It Called Bottom-Up?
We start with the smallest problems:
F(0), F(1) ↓ F(2) ↓ F(3) ↓ F(4) ↓ F(5) ↓ F(6)
and gradually build the solution.
Therefore:
Bottom-up = Start with the smallest sub-problems and build toward the original problem.
13. Memoization vs Tabulation
| Aspect | Memoization | Tabulation |
|---|---|---|
| Approach | Top-down | Bottom-up |
| Uses | Usually recursion | Usually iteration/loops |
| Starting point | Original problem | Smallest sub-problems |
| Storage | Dictionary/array | Usually an array/table |
| Only needed states | Can calculate only states that are actually reached | Usually fills all required states |
| Recursion stack | Yes | No |
| Implementation | Often easier when recurrence is naturally recursive | Often more efficient and iterative |
| Example | Recursive Fibonacci + memo | Iterative Fibonacci + table |
14. Steps for Solving a Problem Using DP
When students encounter a DP problem, they can follow these steps.
Step 1: Identify the Sub-Problems
Ask:
Can I break this problem into smaller versions of the same problem?
For Fibonacci:
F(n) ↓ F(n-1) and F(n-2)
Step 2: Check for Overlapping Sub-Problems
Ask:
Will the same sub-problem be calculated more than once?
If yes, storing the answer may help.
Step 3: Check for Optimal Substructure
For optimization problems, ask:
Can the optimal solution be constructed from optimal solutions to smaller problems?
For shortest paths, for example, the optimal route contains optimal sub-routes.
Step 4: Define the State
A state represents the information needed to describe a sub-problem.
For Fibonacci:
dp[n]
means:
The Fibonacci number at position
n.
For other problems, the state could be more complex, such as:
dp[i] dp[i][j] dp[i][capacity]
Step 5: Define the Recurrence Relation
The recurrence describes how to calculate a larger state from smaller states.
For Fibonacci:
This is the relationship that allows us to build the solution.
Step 6: Identify the Base Cases
The base case is the smallest problem that can be solved directly.
For Fibonacci:
Step 7: Choose the DP Approach
Choose either:
Memoization → Top-Down
or
Tabulation → Bottom-Up
Step 8: Construct the Final Solution
Use the stored sub-problem results to obtain the answer to the original problem.
15. A Classic Example: Minimum-Cost Route
Suppose you want to travel from:
A → D
and the possible roads are:
A → B → D A → C → D A → B → C → D
Each road has a cost.
Suppose:
A → B = 5 B → D = 7 A → C = 3 C → D = 10
Then:
A → B → D = 5 + 7 = 12 A → C → D = 3 + 10 = 13
Therefore:
Minimum cost = 12
The larger problem can be solved using smaller route problems.
This type of thinking leads to important DP algorithms for shortest paths and other optimization problems.
16. Advantages of Dynamic Programming
1. Reduces repeated computation
This is the biggest advantage.
2. Improves efficiency
A problem that takes exponential time using naive recursion can sometimes be reduced to polynomial or even linear time.
For Fibonacci:
Naive recursion → approximately O(2ⁿ) DP → O(n)
3. Useful for optimization
DP is widely used for:
- shortest paths,
- resource allocation,
- scheduling,
- sequence problems,
- knapsack-type problems,
- text processing,
- many optimization problems.
4. Produces optimal solutions
When the problem satisfies the required DP properties and the recurrence is correctly formulated, DP can find an optimal solution.
17. Disadvantages of Dynamic Programming
1. Uses additional memory
The algorithm needs to store intermediate results.
2. State definition can be difficult
Students often find it challenging to determine:
“What exactly should
dp[i]ordp[i][j]represent?”
3. Recurrence relation can be difficult
Finding the correct relationship between states requires careful problem analysis.
4. Not every problem is suitable for DP
If there are no overlapping sub-problems or no suitable optimal substructure, DP may not provide an advantage.
18. Dynamic Programming and Divide and Conquer
These two strategies are related, but they are not the same.
| Divide and Conquer | Dynamic Programming |
|---|---|
| Divides a problem into smaller sub-problems | Divides a problem into smaller sub-problems |
| Sub-problems are usually independent | Sub-problems often overlap |
| Usually doesn't need to store every sub-problem result | Stores sub-problem results |
| May solve the same sub-problem repeatedly in some cases | Avoids repeated computation |
| Example: Merge Sort | Example: Fibonacci, Knapsack |
Key distinction
Divide and Conquer: Solve smaller problems separately.
Dynamic Programming: Solve smaller problems and remember their answers because they may be needed again.
19. Dynamic Programming and Recursion
They are also not opposites.
Think of them this way:
Recursion ↓ A technique for defining a problem in terms of smaller versions of itself
Whereas:
Dynamic Programming ↓ A strategy for solving overlapping sub-problems efficiently by storing results
Memoization actually combines both:
Recursion + Storage ↓ Memoization ↓ Dynamic Programming
20. A Very Simple Analogy for Students
Imagine you are solving a large assignment.
While solving it, you calculate:
Question 1 → Answer = 25
Later, another question requires the answer to Question 1.
Without DP:
You calculate Question 1 again.
With DP:
You look at your notebook:
Question 1 → 25
and reuse the answer.
So:
The notebook is the DP table.
This is perhaps the simplest way to explain the core idea of DP to beginners.
21. The Three Keywords Students Should Remember
For an introductory algorithmic-thinking course, I would emphasize these three words:
1. OVERLAP
The same sub-problems occur repeatedly.
2. STORE
Save the answers of solved sub-problems.
3. REUSE
Use the stored answers instead of solving them again.
Therefore:
⭐ Summary
Dynamic Programming is a problem-solving strategy that divides a problem into smaller overlapping sub-problems, solves each sub-problem only once, stores its result, and reuses the stored results to efficiently solve the original problem.
And the two essential properties are:
while the two implementation approaches are:
Some Examples:
The Knapsack Problem
The knapsack problem is a classical example of a problem that can be solved using dynamic programming. The problem is defined as follows:
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. Each item can only be taken once.
Consider the following example:
We want to find the maximum value we can carry in the knapsack. For this example, the maximum value we can carry in the knapsack of capacity 50 is 220.
Longest Common Subsequence (LCS):
Dynamic Programming offers a more efficient approach by dividing the problem into smaller subproblems and using memoization or tabulation to store intermediate results.
Comments
Post a Comment