Skip to content

Dynamic programming

In the context of programming, it is an optimization technique developed by Richard Bellman in the 1950s. It can be applied to a specific class of recursive problems. For example, calculation of Fibonacci numbers or finding the shortest path in a graph.

In general, it allows to turn algorithms with exponential complexity to polynomial complexity (but may require more space). I won’t go into more details - but very primitively it boils down to memoization and cycle detection.

You can watch this MIT course where it’s explained better.