Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively. Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure. Dynamic programming is one way to solve problems with these properties. The process of breaking a complicated problem down into simpler sub-problems is called "divide and conquer".
Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial.
Dynamic Programming algorithm is designed using the following four steps −
- Characterize the structure of an optimal solution.
- Recursively define the value of an optimal solution.
- Compute the value of an optimal solution, typically in a bottom-up fashion.
- Construct an optimal solution from the computed information.
- Matrix Chain Multiplication
- Longest Common Subsequence
- Travelling Salesman Problem
- Fibonacci Sequence
- Nth Fibonacci
- Nth Catalan Number/Sequence
- Longest Common Subsequence
- Longest Increasing Subsequence
- Longest Common Substring
- Longest Palindromic Substring
- Knapsack Problem
- Edit Distance
- Coin Change
- Matrix Chain Multiplication
- Balanced Tree Count
- Counting Hops
- Floyd Warshall Algorithm
- Gold Mine Problem
- Least Common Multiple (LCM)
- Painting Fence Algorithm
- Staircase
- Subset Sum Problem