Skip to main content

​
Overview

Dynamic programming in DSA is a technique where you break a problem into smaller overlapping subproblems, solve each subproblem once, and reuse those results instead of recalculating them.

​
Two Main DP Styles

Top-down (memoization): Solve the problem recursively and store the results of solved subproblems to avoid redundant calculations. Bottom-up (tabulation): Solve smaller subproblems first, store results in a table, and use them to build solutions to larger problems.

​
Examples

​
Fibonacci

function fib(n, cache = new Map()) {
  if (n <= 1) return n;

  if (cache.has(n)) {
    return cache.get(n);
  }

  const result = fib(n - 1, cache) + fib(n - 2, cache);
  cache.set(n, result);

  return result;
}

console.log(fib(6)); // 8
console.log(fib(10)); // 55
console.log(fib(999)); // 2.686381002448534e+208
  • Top-down - Time: O(n), Space: O(n)
  • Bottom-up - Time: O(n), Space: O(1)

Build docs developers (and LLMs) love

Get started for freeTalk to us