Dynamic Programming
Dynamic Programming
Dynamic Programming (DP) is one of the most important problem-solving techniques in Algorithm Design and Analysis. It is especially useful for problems where the same smaller problems are solved repeatedly.
1. What is Dynamic Programming?
Dynamic programming is a technique for solving a problem by:
- Breaking it into smaller subproblems.
- Solving each subproblem only once.
- Storing the result of each subproblem.
- Reusing the stored results whenever the same subproblem occurs again.
The main idea is:
Don't solve the same problem again—remember the answer when you solve it the first time.
2. Dynamic Programming and Divide-and-Conquer
Dynamic programming is closely related to divide and conquer.
In divide and conquer:
Problem / \ Subproblem Subproblem / \ smaller smaller
The subproblems are generally independent.
For example, in merge sort:
[1 2 3 4 5 6 7 8] | --------------------- | | [1 2 3 4] [5 6 7 8]
The two subproblems do not need to solve the same smaller problem.
3. The Important Difference: Overlapping Subproblems
Dynamic programming is useful when the subproblems overlap.
That means:
The same subproblem appears multiple times while solving the larger problem.
Consider Fibonacci numbers.
For example:
and
Notice that:
F(3)is calculated more than once.
The recursive calculation looks like:
F(5) / \ F(4) F(3) / \ F(3) F(2)
The same F(3) occurs in multiple places.
This is called overlapping subproblems.
4. Why Repeated Computation Is a Problem
Suppose we calculate Fibonacci numbers using the straightforward recursive method.
F(n) ├── F(n-1) │ ├── F(n-2) │ └── F(n-3) │ └── F(n-2) ├── F(n-3) └── F(n-4)
Notice that F(n-2) and F(n-3) are repeatedly calculated.
As n becomes larger, the amount of repeated work becomes very large.
Dynamic programming avoids this repetition.
5. The Basic Idea of DP
Suppose we calculate:
F(0),F(1),F(2),F(3),F(4),F(5)Instead of calculating the same value repeatedly, we store the results:
| n | F(n) |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
Once F(3) has been calculated, we simply look it up whenever we need it.
So the basic principle is:
Calculate → Store → Reuse
6. Why Is It Called "Dynamic Programming"?
The word programming here does not mean writing computer programs.
In the CLRS context, programming refers to a tabular method of computation.
The algorithm typically builds a table such as:
+-----+-----+-----+-----+-----+ | 0 | 1 | 1 | 2 | 3 | +-----+-----+-----+-----+-----+
The table contains solutions to smaller subproblems.
These solutions are then used to solve larger subproblems.
7. Dynamic Programming Is Mainly Used for Optimization Problems
Dynamic programming typically applies to optimization problems.
An optimization problem may have many possible solutions.
Each solution has a value.
We want the solution with the:
- minimum value, or
- maximum value.
For example:
Minimum
Find the cheapest way to travel from A to B.
Maximum
Find the maximum profit obtainable by cutting a rod.
The important point is that there may be more than one optimal solution.
Therefore, it uses the phrase:
an optimal solution
rather than necessarily saying the optimal solution.
8. A Simple Real-Life Example
Imagine that you have ₹100 and several items to buy.
You want to select items so that you obtain the maximum possible benefit without exceeding ₹100.
There may be many combinations:
Combination 1 → benefit 80 Combination 2 → benefit 95 Combination 3 → benefit 90 Combination 4 → benefit 95
The maximum benefit is:
95There may be two different combinations that give 95.
Dynamic programming helps systematically find such an optimal value.
9. Two Important Properties of Dynamic Programming
For dynamic programming to be useful, two characteristics are particularly important.
1. Overlapping subproblems
The problem should contain subproblems that are solved repeatedly.
Problem / \ A B / \ / \ C D C E
Here C occurs more than once.
Instead of solving C twice:
solve C solve C again
DP does:
solve C store C reuse C
2. Optimal substructure
An optimal solution to the overall problem can be constructed from optimal solutions to its subproblems.
In simple terms:
The best solution to the big problem contains best solutions to appropriate smaller problems.
This property allows us to build an optimal solution systematically from smaller optimal solutions.
10. Four Steps for Developing a Dynamic Programming Algorithm
Following gives a very useful four-step procedure.
Step 1 — Characterize the structure of an optimal solution
First determine:
What does an optimal solution look like?
We identify how the optimal solution is related to solutions of smaller problems.
Step 2 — Recursively define the value of an optimal solution
Next, formulate a recurrence describing the optimal value.
For example:
The recurrence tells us how to calculate the solution of a larger problem from smaller problems.
Step 3 — Compute the value of an optimal solution
Instead of repeatedly using recursion, calculate the subproblems and store their answers.
Usually this is done bottom-up.
For example:
Smallest problems ↓ larger problems ↓ still larger problems ↓ original problem
Step 4 — Construct an optimal solution
Once the optimal values have been computed, we can reconstruct the actual solution.
For example, if the problem asks:
What is the maximum profit?
we may only need the table of values.
But if it asks:
Which items should be selected to obtain the maximum profit?
then we need additional information to reconstruct the solution.
11. Value vs. Actual Solution
This distinction is very important for students.
Suppose a DP algorithm produces:
This tells us the value of the optimal solution.
But we may also want to know:
Which choices produced 100?
Therefore, we distinguishes between:
Finding the optimal value
DP table → optimal value
and
Constructing the optimal solution
DP table + additional information ↓ actual solution
If only the optimal value is required, the fourth step can sometimes be omitted.
12. Bottom-Up Dynamic Programming
One common approach is bottom-up dynamic programming.
We start with the smallest subproblems and gradually solve larger ones.
For example:
Size 0 ↓ Size 1 ↓ Size 2 ↓ Size 3 ↓ Size 4 ↓ Size n
At each stage, previously calculated results are available.
This avoids recursion and repeated computation.
13. Top-Down Dynamic Programming
Another approach is top-down dynamic programming with memoization.
We start with the original problem.
When a subproblem is encountered:
- Check whether its answer is already stored.
- If yes, reuse it.
- If not, solve it.
- Store the answer.
For example:
F(5) / \ F(4) F(3) | ...
If F(3) has already been calculated:
F(3) → stored value
we do not calculate it again.
This is called memoization.
14. Bottom-Up vs. Top-Down
| Feature | Top-Down | Bottom-Up |
|---|---|---|
| Approach | Recursive | Iterative |
| Technique | Memoization | Tabulation |
| Starts with | Original problem | Smallest subproblem |
| Stores results | Yes | Yes |
| Repeated computation | Avoided | Avoided |
| Recursion | Usually used | Not required |
Both approaches use the central idea:
Solve each subproblem once and store its result.
15. Dynamic Programming Examples
The following are some important applications.
1. Rod Cutting
Given a rod of length n and prices for different lengths, determine how to cut the rod to obtain maximum revenue.
Rod -------------------------------- length n
Possible cuts:
n ↓ 1 + (n-1) 2 + (n-2) 3 + (n-3) ...
Dynamic programming determines the combination that gives maximum revenue.
2. Matrix-Chain Multiplication
Suppose we have:
A1A2A3A4Matrix multiplication is associative:
(A1A2)A3and
A1(A2A3)produce the same mathematical result.
But the number of scalar multiplications can be very different.
Dynamic programming finds the parenthesization requiring the minimum number of scalar multiplications.
3. Longest Common Subsequence
Given two sequences:
X = ABCBDAB Y = BDCABA
we may want to find the longest sequence that occurs in both while preserving the order of characters.
Dynamic programming solves the Longest Common Subsequence (LCS) problem efficiently.
4. Optimal Binary Search Trees
Suppose some search keys are accessed much more frequently than others.
We want to construct a binary search tree that minimizes the expected search cost.
Dynamic programming can determine an optimal binary search tree.
16. Dynamic Programming vs. Divide and Conquer
This is one of the most important comparisons for an undergraduate course.
| Divide and Conquer | Dynamic Programming |
|---|---|
| Divides problem into subproblems | Decomposes problem into subproblems |
| Subproblems generally independent | Subproblems overlap |
| Same subproblem usually not repeated | Same subproblem may occur many times |
| Recursive solutions common | Bottom-up or memoized solutions |
| Does not normally store all subproblem results | Stores subproblem results |
| Example: Merge Sort | Example: Rod Cutting |
The key distinction is:
Overlapping subproblems17. A Simple Way to Remember Dynamic Programming
For undergraduate students, I would summarize DP with this four-word principle:
Break → Solve → Store → Reuse
More precisely:
Original Problem | Break into subproblems ↓ Solve each subproblem ↓ Store the result ↓ Reuse the result ↓ Solve larger problem ↓ Obtain final answer
18. Summary
definition:
Dynamic programming is an algorithm design technique used primarily for optimization problems in which the problem has overlapping subproblems and optimal substructure. It solves each subproblem once, stores its result, and reuses the stored result to efficiently construct the solution to the original problem.
In one sentence:
Dynamic Programming = Solve once + Store + ReuseThis is the central idea that students should understand before moving on to Dynamic Programming Problems like Rod Cutting, Matrix-Chain Multiplication, LCS, and Optimal Binary Search Trees.
Comments
Post a Comment