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
5
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));
Output
5