Dynamic programming is a optimization technique used to solve problems by breaking them down into smaller sub-problems and storing the solutions to these sub-problems in a table. This allows for the solutions to be reused, reducing the number of computations required and improving the efficiency of the algorithm.
Dynamic programming is commonly used to solve problems that exhibit overlapping sub-problems, where a recursive solution would require solving the same sub-problem multiple times. By using dynamic programming, the solutions to these sub-problems are stored in a table, reducing the time complexity of the algorithm.
Dynamic programming is used to solve problems such as the Fibonacci sequence, the longest common subsequence, and the knapsack problem. It can also be used in combination with other techniques, such as greedy algorithms and backtracking, to solve complex problems.
There are two main types of dynamic programming: memoization and tabulation. In memoization, solutions to sub-problems are stored in a table as they are computed, and reused when needed. In tabulation, all solutions to sub-problems are computed in a bottom-up manner, filling the table from smaller sub-problems to larger ones.
Dynamic programming algorithms have time complexity that is often polynomial, and can be much faster than exponential-time algorithms such as brute force search. However, dynamic programming algorithms can also have a high space complexity, as they require a table to store the solutions to sub-problems.