Dynamic programming is an optimization of Divide-and-Conquer Paradigm.

Similar to divide-and-conquer, dynamic programming algorithms split the problem into related sub-problems. Solutions to sub-problems can be used in other to sub-problems. In this way, the final solution is created by ‘building’ on to subproblems.

An algorithmic problem can be solved with a DP approach if a recurrence relation can be identified, and it is known that the sub-problems overlap. A way to check for overlapping can be to use a recursion tree to show the recursive function calls, and look for any common calls.

The criteria for a solution to be considered a DP solution is:

  • Breaking down problems into sub-problems
  • Solutions of sub-problems are overlapping i.e. a sub-solution can solve/aid in solving multiple sub-problems.

In most cases, DP is used to solve optimisation problems.

Memoization

Memoization is the process of storing solutions of sub-problems, such that they can be looked up for future sub-problems. It is considered a ‘bottom-up’ approach, since sub-problems of minimal sizes are cached first.