Dynamic Programming (7 Marks – RGPV)
Dynamic Programming (DP)
Definition
Dynamic Programming (DP) is an algorithm design technique used to solve optimization and decision
problems by breaking them into smaller overlapping subproblems, solving each subproblem only once,
and storing its result for future use.
The stored results are reused whenever required, avoiding repeated calculations and reducing execution
time.
Simple Definition (Easy to Remember):
Dynamic Programming is a technique that solves a problem by dividing it into smaller overlapping
subproblems, storing their solutions, and reusing them to obtain the optimal solution.
Characteristics of Dynamic Programming
1. Overlapping Subproblems
2. The same subproblem is solved multiple times.
3. DP stores the result to avoid repeated computation.
4. Optimal Substructure
5. The optimal solution of the main problem depends on the optimal solutions of smaller subproblems.
6. Memoization
7. Stores the result of subproblems during recursion.
8. Tabulation
9. Solves subproblems iteratively using a table.
10. Optimization Technique
11. Used to obtain the best (minimum or maximum) solution.
1
12. Improves Efficiency
13. Reduces time complexity by avoiding duplicate calculations.
Overlapping Subproblems
A problem has Overlapping Subproblems if the same smaller problems occur repeatedly during
computation.
Example
In Fibonacci,
F(5)
├── F(4)
│ ├── F(3)
│ └── F(2)
└── F(3)
Here, F(3) is calculated more than once.
Dynamic Programming stores the value of F(3) and reuses it whenever required.
Optimal Substructure
A problem has Optimal Substructure if the optimal solution of the original problem can be obtained from
the optimal solutions of its smaller subproblems.
Example
In 0/1 Knapsack, the optimal solution for capacity W depends upon the optimal solutions of capacities
smaller than W.
Algorithm
Step 1: Identify the problem having overlapping subproblems.
Step 2: Divide the problem into smaller subproblems.
Step 3: Solve each subproblem only once.
2
Step 4: Store the result in a table or memory.
Step 5: Reuse stored values whenever required.
Step 6: Combine all subproblem solutions.
Step 7: Obtain the optimal final solution.
Example (Fibonacci using Dynamic Programming)
Find F(6)
Formula:
F(n)=F(n−1)+F(n−2)
DP Table
n 0 1 2 3 4 5 6
F(n) 0 1 1 2 3 5 8
Instead of calculating the same values repeatedly, DP stores them in the table.
Therefore,
F(6) = 8
Time Complexity
Example:
Recursive Fibonacci
O(2ⁿ)
Dynamic Programming Fibonacci
O(n)
3
Space Complexity
O(n)
Advantages
1. Avoids repeated calculations.
2. Produces the optimal solution.
3. Reduces execution time.
4. Efficient for optimization problems.
5. Improves overall algorithm performance.
Disadvantages
1. Requires additional memory.
2. Difficult to identify DP problems.
3. Increases implementation complexity.
4. Not suitable for every problem.
5. Table creation may consume extra space.
Applications
Dynamic Programming is used in:
• Fibonacci Series
• 0/1 Knapsack Problem
• Multi-stage Graph
• Floyd-Warshall Algorithm
• Matrix Chain Multiplication
• Longest Common Subsequence (LCS)
• Shortest Path Problems
• Resource Allocation
• Network Optimization
• Bioinformatics
Difference Between Greedy Method and Dynamic Programming
Greedy Method Dynamic Programming
Makes local optimal choice Solves all required subproblems
4
Greedy Method Dynamic Programming
Does not store results Stores results for reuse
Faster but not always optimal Guarantees optimal solution (when DP applies)
Less memory required More memory required
Example: Huffman, Prim, Kruskal Example: 0/1 Knapsack, Floyd Warshall
Conclusion
Dynamic Programming is one of the most important algorithm design techniques used for solving
optimization problems efficiently. It works by solving overlapping subproblems, storing their solutions,
and reusing them whenever required. Due to its ability to reduce repeated computation and guarantee
optimal solutions, it is widely used in computer science and engineering.
⭐ Keywords for Revision
• Dynamic Programming
• Overlapping Subproblems
• Optimal Substructure
• Memoization
• Tabulation
• Optimization
• Fibonacci
• 0/1 Knapsack
• Floyd-Warshall
• Multi-stage Graph
• O(n)
• Resource Allocation