Dynamic Programming

Dynamic Programming refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. 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 the sub-problems can be recursively nested inside larger problems, then dynamic programming methods are applicable, and then there is a relation between the value of the larger problems and the values of the sub-problems.