Dynamic Programming (DP) is a powerful technique used to solve problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant calculations. It is particularly effective for optimization problems and problems that exhibit overlapping subproblems and optimal substructure.

Process

1. Define the Problem: Clearly define the problem and identify if it can be solved using DP. Look for characteristics such as overlapping subproblems and optimal substructure.

2. Recursive Approach: Break down the problem into smaller subproblems using recursion. Define the base cases. Express the solution to the problem in terms of solutions to its subproblems.

3. Memoization (Top-Down Approach): Create a memoization table (usually a dictionary) to store the results of subproblems. Modify the recursive function to check the memoization table before computing the solution. Store the results of subproblems in the memoization table.

4. Tabulation (Bottom-Up Approach): Create a DP table to store the results of subproblems. Initialize the DP table with base cases. Iteratively fill the DP table using the recurrence relation. Extract the solution from the DP table.

When to Use

1. Optimization Problems: DP is commonly used to solve optimization problems where the goal is to find a function's minimum or maximum value.

2. Problems with Overlapping Subproblems: When the same subproblems are solved multiple times, DP can significantly reduce the computation time by storing the results of subproblems.

3. Problems with Optimal Substructure: When the optimal solution to a problem can be constructed from the optimal solutions of its subproblems.

How Does It Reduce Time Complexity?

1. Avoid Redundant Calculations: By storing the results of subproblems in a table, DP avoids redundant calculations, significantly reducing time complexity.

2. Polynomial Time Complexity: DP often reduces the time complexity from exponential to polynomial, making it feasible to solve larger instances of the problem.

Example problem for better understanding

Fibonacci Number

Thank you for reading!

You can support me by buying me a book.