Dynamic Programming

Dynamic Programming:- Dynamic programming is both a mathematical optimization method and a computer programming method.
Dynamic Programming (DP) is a method of solving problems by breaking them down into smaller, overlapping subproblems, and storing the solutions to these subproblems in a table (or array) to avoid redundant computation. This technique is often used for optimization problems, where the goal is to find the best solution among a set of possible solutions.
DP can be applied to both discrete and continuous problems, and is particularly useful for solving problems with overlapping subproblems, such as finding the shortest path in a graph or the longest common subsequence of two strings.
In DSA, Dynamic Programming is used to solve problems that have overlapping subproblems, such as:
Fibonacci series
Shortest path in a graph
Longest Common Subsequence
Longest Increasing Subsequence
Matrix Chain Multiplication
Knapsack problem
DP can be implemented using two methods:
Memoization: store the solutions to subproblems in a table (or array) as they are solved, so that they can be reused later without having to be recomputed.
Tabulation: fill in a table (or array) by starting with the smallest subproblems and working up to the larger ones.
DP is generally considered to be a bottom-up approach, as it starts with the smallest subproblems and builds up to the larger ones.