Those who cannot remember the past are condemned to repeat it.
— George Santayana

The Fibonacci sequence is defined as follows:

\[F_1 = F_2 = 1\]
\[F_n = F_{n−1} + F_{n−2}\]

Let’s write a program to find the nth Fibonacci number.

Notice, some of the numbers are repeatedly evaluated thus this algorithm takes a large amount of running time (exponential). Let’s store the numbers in a dictionary after calculation then we’ll look up the number in the dictionary before evaluation to save time.

The above technique of using a look-up table is called memoization. This process of using a memoization based algorithm is dynamic programming. The running time of dynamic programming is given by

\[time = \text{number of subproblems} * time / \text{subproblem} = n * \theta(1) = \theta(n)\]

In fact, here we used a top-down approach by solving the subproblems we encountered while solving the problem, there also exists a bottom-up approach of dynamic programming where we first solve all the subproblems before arriving at the problem itself.

A problem must possess the following characteristics in order to be solvable by dynamic programming:

Optimal substructure: A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems.

Overlapping subproblems: When the solution of some of the subproblems are same i.e. subproblems share their solutions, they are said to be overlapping. That is, a recursive algorithm for the problem solves the same subproblem repeatedly.

Writes down “1+1+1+1+1+1+1+1 =” on a sheet of paper.
“What’s that equal to?”
Counting “Eight!”
Writes down another “1+” on the left.
“What about that?”
“Nine!” “ How’d you know it was nine so fast?”
“You just added one more!”
“So you didn’t need to recount because you remembered there were eight! Dynamic Programming is just a fancy way to say remembering stuff to save time later!”
— Quora answer^{1}

Dynamic programming differs from greedy algorithms in one aspect, that is, it first find the optimal solution to subproblems then make the choice while greedy algorithms first make a greedy choice then solve the subproblems.

Algorithms solvable using Dynamic programming paradigm: