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

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

Approach 1: Recursion


Approach 2: Memoization/Top-down Dynamic Programming

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


Approach 3: Tabulation/Bottom-up Dynamic Programming

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