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
- What is Dynamic Programming?
- What is memoization?
- What is tabulation?
- What are overlapping subproblems?