Dynamic Programming Optimal Substructure
A problem has optimal substructure if its sub-problems have optimal solutions that constitute the problem’s optimal solution. This type of problem can be solved using dynamic programming.
Dynamic programming is a technique to optimize algorithms by breaking a problem with overlapping sub-problems into smaller sub-problems and then combining the solutions to the sub-problems to solve the larger problem.
Dynamic programming is both a mathematical optimization method and a computer programming method. It simplifies a complicated problem by breaking it down into simpler sub-problems.
It can be applied to combinatorial and optimization problems such as finding the shortest path between two points or finding the smallest set of objects that satisfies some criteria.
Dynamic Programming Problem Variable
When solving a problem with dynamic programming, we maintain a dynamic set of variables corresponding to each sub-problem that changes in order to find the overall solution. These variables are called problem variables.