What is Dynamic Programming?

Dynamic Programming is a way of solving a problem by breaking it down into smaller sub problems and storing them without having to recalculate them. Usually this involves 3 main methods.

Recursion (method invoking itself)
Memoization (Storing intermediate results, not to be confused with memorization)
Bottom Up Approach

Example: Fibonacci Series

function getFib(n) {
  if (n == 1 || n == 2)
    return 1;
  return getFib(n - 1) + getFib(n - 2);
}

console.log(getFib(5));

Output

Demo

In the above problem, we are using recursion, and getFib(3) gets called twice once by getFib(3) and other time by getFib(4). It needs to be computed twice if we don’t store the intermediate results. So lets store them now to avoid recalculation.

var memo = [];

function getFib(n) {
  if (memo[n])
    return memo[n];
  if (n == 1 || n == 2)
    return 1;
  memo[n] = getFib(n - 1) + getFib(n - 2);
  return memo[n];
}

console.log(getFib(5));

Demo

Output

Related