The name "Dynamic Programming" is a misnomer.

Motto of Dynamic Programming

Dynamic Programming (DP) is a algorithm design paradigm that includes the following features:

  1. Algorithms are recursive
  2. There are overlapping recursive subproblems
  3. Memoization can be used to reduce re-solving overlapping subproblems
  4. You can also write an iterative solution which can be easier to analyze

Think of DP as a "filling in a table" problem

To devise a DP solution to a problem, you must