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.
If sub-problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub-problems. In the optimization literature, this relationship is called the Bellman equation.
What is Dynamic Programming Strategy?
- Recursion: Solves subproblems recursively
- Memoization: Stores already computed values in a table.
Properties of Dynamic Programming Strategy:
- Optimal Substructure: an optimal solution to a problem contains optimal solutions to subproblems.
- Overlapping Subproblems: a recursive solution contains a small number of distinct subproblems repeated many times.
Dynamic Programming Approaches:
- Bottom-up dynamic programming
- Top-down dynamic programming
Examples of dynamic programming algorithms:
- Find Minimum Path Sum in a given 2D Array.
- Calculate all Unique Path count can be taken by Robot
- Find Total Number of Set Having given Combination Sum.
- Maximize House Robbery Amount that can be made.
- Find total ways to reach the nth stair using step 1, 2 or 3.
- Cutting Rod Problem to get maximum profit
- Find Longest Increasing Subsequence
