Dynamic Programming

Dynamic Programming is a technique that trades space for time. It stores the intermediate results computed (which might be needed in future) in memory, thus avoiding the need to compute the result every time.

It is typically used when your problem can be divided into states and the solution to the problem as a whole can be derived from the solution to sub-problems.

The considered problem may have either overlapping problems or optimal substructure characteristics.

What is overlapping problems?

A problem is said to have overlapping sub problems if it can be broken down into sub problems which are reused multiple times. This is closely related to recursion.

What is an Optimal Substructure?

Optimal Substructure: A given problems has Optimal Substructure Property if optimal solution of the given problem can be obtained by using optimal solutions of its sub problems.

Read more at Grouply