Dynamic Programming

1. Fibonacci Sequence: Compute the nth Fibonacci number efficiently using a table to store previously computed values.

2. Longest Common Subsequence: Find the longest subsequence that appears in two sequences.

3. Knapsack Problem: Determine the maximum value that can be obtained by selecting items with given weights and values, subject to a weight constraint.

4. Matrix Chain Multiplication: Determine the optimal order of multiplying a sequence of matrices to minimize the number of scalar multiplications.

5. Edit Distance: Calculate the minimum number of operations (insertions, deletions, substitutions) required to transform one string into another.

6. Optimal Binary Search Trees

7. Rod Cutting Problem

8. Longest Increasing Subsequence

9. Coin Change Problem

1. A method for solving problems by breaking them down into smaller subproblems and solving them independently. (Optimal substructure)

2. The solutions to the subproblem are stored in memory and reused to solve the larger problem. (Overlapping subproblems)

==> Lead to significant improvements in performance compared to solving the problem from scratch each time.

1. We can solve the subproblems efficiently and reuse their solutions.

2. We can avoid redundant work and reduce the time complexity of the overall problem.

1. Identify the optimal substructures:

   • Define subproblems: Break down the problem into smaller subproblems that can be solved independently.

   • Define the base case: Determine the solutions to the simplest subproblems.

2. Define the recurrence relation: Express the solution to each subproblem in terms of the solutions to smaller subproblems.

3. Compute the subproblem solutions: Use the recurrence relation to compute the solutions to the subproblems, storing them in memory as needed.

4. Build the solution: Combine the solutions to the subproblems to form the solution to the original problem.

1. Advantages: Dynamic programming guarantees an optimal solution by avoiding redundant calculations and exploring all possible subproblems.

2. Disadvantages: It might require a significant amount of memory to store solutions to subproblems in a table. In some cases, identifying the optimal substructure and recursive relation can be challenging.