Dynamic Programming
Introduction
Dynamic Programming (DP) is an algorithm design technique used to solve complex optimization and decision-making problems by dividing them into smaller overlapping subproblems. Instead of solving the same subproblem repeatedly, Dynamic Programming stores the computed results and reuses them whenever required. This significantly reduces the execution time and improves the efficiency of the algorithm.
The concept of Dynamic Programming was introduced by Richard Bellman in the 1950s. It is widely used in optimization problems where the solution of a larger problem depends upon the solutions of smaller subproblems.
Why Do We Need Dynamic Programming?
Many recursive algorithms repeatedly solve the same subproblems, resulting in unnecessary computations. Dynamic Programming eliminates this repetition by storing intermediate results. Consequently, the overall execution time is greatly reduced.
| Without Dynamic Programming | With Dynamic Programming |
|---|---|
| Repeated calculations | Each subproblem solved only once |
| Higher execution time | Faster execution |
| Recursive overhead | Efficient use of stored results |
| Large number of function calls | Reduced function calls |
Bellman's Principle of Optimality
The foundation of Dynamic Programming is Bellman's Principle of Optimality, which states that:
This means that if the best solution to a larger problem is known, then every part of that solution must also be the best possible solution for its corresponding subproblem.
Characteristics of Dynamic Programming
| Characteristic | Description |
|---|---|
| Optimal Substructure | The optimal solution is constructed from optimal solutions of smaller subproblems. |
| Overlapping Subproblems | The same subproblems are solved multiple times. |
| Memoization | Stores previously computed results. |
| Tabulation | Builds the solution from bottom to top using a table. |
Working Principle
Dynamic Programming solves a problem by dividing it into smaller subproblems, solving each subproblem only once, storing the solution, and using the stored solution whenever required. This avoids repeated computations and improves overall efficiency.
Real-Life Example
Suppose you are climbing a staircase having 10 steps. You can climb either one step or two steps at a time. While calculating the total number of possible ways, several smaller calculations are repeated. Dynamic Programming stores these intermediate answers so that each calculation is performed only once.
Example
| Step Number | Ways to Reach |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 5 |
| 5 | 8 |
Instead of calculating the number of ways repeatedly, Dynamic Programming stores the previous values and directly uses them whenever needed.
Memoization and Tabulation
Dynamic Programming can be implemented using two different approaches: Memoization and Tabulation. Both techniques avoid repeated calculations by storing the solutions of subproblems.
| Memoization (Top-Down) | Tabulation (Bottom-Up) |
|---|---|
| Uses recursion. | Uses iteration. |
| Computes values only when required. | Computes all values in advance. |
| Stores results in memory. | Stores results in a table. |
| Easy to convert from recursive solutions. | Usually faster because recursion overhead is eliminated. |
Dynamic Programming Algorithm
DynamicProgramming(Problem)
Step 1 : Divide the problem into smaller subproblems.
Step 2 : Check whether the solution of a subproblem already exists.
Step 3 : If available, reuse the stored solution.
Step 4 : Otherwise, solve the subproblem.
Step 5 : Store the computed result.
Step 6 : Repeat until the complete problem is solved.
Step 7 : Return the optimal solution.
Complexity Analysis
| Technique | Time Complexity | Space Complexity |
|---|---|---|
| Simple Recursion | Usually Exponential | Depends on recursion depth. |
| Memoization | Polynomial (Problem Dependent) | Extra memory for cache. |
| Tabulation | Polynomial (Problem Dependent) | Table required for storing solutions. |
Advantages of Dynamic Programming
- Avoids repeated computation of the same subproblems.
- Significantly improves execution time.
- Produces optimal solutions for many optimization problems.
- Widely used in competitive programming and technical interviews.
- Suitable for solving large and complex optimization problems.
Limitations of Dynamic Programming
- Requires additional memory for storing intermediate results.
- Not every problem can be solved using Dynamic Programming.
- Identifying overlapping subproblems may be difficult.
- Implementation may become complex for beginners.
Applications of Dynamic Programming
| Application | Description |
|---|---|
| 0/1 Knapsack Problem | Maximizing profit under weight constraints. |
| Shortest Path Problems | Floyd-Warshall Algorithm. |
| Resource Allocation | Optimal allocation of limited resources. |
| Bioinformatics | DNA and protein sequence alignment. |
| Artificial Intelligence | Planning and optimization problems. |
Dynamic Programming vs Divide and Conquer
| Dynamic Programming | Divide and Conquer |
|---|---|
| Subproblems overlap. | Subproblems are independent. |
| Stores intermediate results. | Does not store intermediate results. |
| Avoids repeated computation. | May recompute the same subproblems. |
| Uses Memoization or Tabulation. | Uses recursion only. |
Summary
Dynamic Programming is one of the most powerful algorithm design techniques used for solving optimization problems efficiently. By storing the solutions of overlapping subproblems, it avoids repeated computations and significantly reduces execution time. The two implementation techniques, Memoization and Tabulation, make Dynamic Programming suitable for solving a wide variety of real-world problems such as the 0/1 Knapsack Problem, Floyd-Warshall Algorithm, Resource Allocation, Bioinformatics and Artificial Intelligence.