Dynamic Programming is a method for solving a problem by breaking it down into subproblems of the same type with smaller input and storing the computed results of overlapping subproblems to reuse them and save time later

Dynamic Programming is an optimization over recursive algorithm with two approaches, top-down/memoization and bottom-up/tabulation

Let's see a specific example

The Fibonacci numbers

The Fibonacci numbers form a sequence such that each number is the sum of two preceding ones, starting from 0 and 1

F0 = 0, F1 = 1
Fn = Fn-1 + Fn-2 for n > 1

Problem

Given a number n, write an algorithm to print the value of Fibonacci number Fn

Recursion approach


Memoization/Top-down approach

Using an array to store computed results starting from N to 0, so called top-down


Tabulation/Bottom-up approach

Using an array to store computed results starting from 0 to N, so called bottom-up