DSA Lesson 26 of 33

Dynamic Programming

Learn how DP solves problems by storing results of smaller subproblems.

Course Progress79%

Theory

Dynamic Programming is a technique for solving problems that contain overlapping subproblems and optimal substructure. Instead of repeatedly solving the same subproblem, we store previously calculated results. Two common approaches are memoization and tabulation.

Example

function fibonacci(n, memo = {}) { if (n <= 1) return n; if (memo[n] !== undefined) { return memo[n]; } memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo); return memo[n]; } console.log(fibonacci(10));

Expected Output

55

Practice

Implement Fibonacci using both memoization and tabulation.

Interview Questions

  1. What is Dynamic Programming?
  2. What is memoization?
  3. What is tabulation?
  4. What are overlapping subproblems?