Concept of Dynamic Programming

What is dynamic programming.

Dynamic programming approach is similar to divide and conquer in breaking down the problem into smaller and yet smaller possible sub-problems. But unlike divide and conquer, these sub-problems are not solved independently. Rather, results of these smaller sub-problems are remembered and used for similar or overlapping sub-problems.

Key concepts of dynamic programming.

1. Optimal substructure: Problem can be constructed from the optimal solutions to its subproblems. Think of it like this: if you want to find the shortest path between two cities, the Shortest path between any two intermediate cities on that route must also be the Shortest path between those two intermediate cities.

2. Overlapping subproblems: A problem has overlapping subproblems if the same subproblems are encountered Multiple times when solving the overall problem using a recursive approach. Consider the Fibonacci sequence: to calculate fib(5), you’d calculate fib(4) and Fib(3). To calculate fib(4), you’d calculate fib(3) and fib(2). Notice how fib(3) is Calculated twice. Dynamic programming aims to calculate fib(3) only once and store Its value for later use.

Approach of dynamic programming.

There are two primary ways to implement dynamic programming.

1.Top-Down Approach (Memorization):

1. This approach starts with the original problem and breaks it down into smaller subproblems recursively.
2.  Before solving a subproblem, it checks if the solution has already been computed and stored in the dp table.
3.  If the solution is already available, it’s retrieved directly. Otherwise, the subproblem is solved, and its solution is stored in the table before being returned.
4.  Memorization adds “memory” (the dp table) to a recursive solution.

Example of top-down(Memorization):

2. Bottom-Up Approach (Tabulation):

1.  This approach starts by solving the smallest subproblems first and then uses their solutions to build up the solutions to larger subproblems, eventually reaching the solution to the original problem.
2. It systematically fills the dp table in a specific order, ensuring that the solutions to all necessary subproblems are available when needed.
3.  Tabulation is often more efficient in terms of function call overhead compared to memorization.

Example of bottom-up(Tabulation):

Examples of dynamic programming.

1. Knapsack Problem: Determining the most valuable items that can fit into a knapsack with a given weight limit. 
2. Longest Common Subsequence (LCS): Finding the longest subsequence common to two sequences.
3. Edit Distance: Finding the minimum number of operations (insertions, deletions, or substitutions) required to transform one string into another.
4. Matrix Chain Multiplication: Finding the most efficient way to multiply a sequence of matrices.
5. Coin Change Problem: Finding the minimum number of coins needed to make a certain amount.
6. Shortest Path Algorithms (like Floyd-Warshall):Finding the shortest paths between all pairs of vertices in a graph.

Advantages of dynamic programming.                                                 

1. Efficiency gain: For addressing difficult problems, dynamic programming may significantly reduce time complexity compared to the naïve technique.
2. Dynamic programming ensures that issues that adhere to the notion of optimality find optimal solutions.

Disadvantages of dynamic programming.

1. High memory usage: When working with bigger input sizes, dynamic programming uses a lot of memory to hold answers to sub-problems.
2. Finding the appropriate sub-problems can be difficult, and doing so frequently necessitates a deep understanding of the main issue at hand.