Dynamic Programming (DP) Fundamentals

Dynamic Programming is an optimization technique used for problems with Overlapping Subproblems and Optimal Substructure. It works by solving each subproblem once and storing the result to avoid redundant work.

1. Memoization (Top-Down)

Memoization is basically "Recursion + Caching." You start solving the original problem and recursively call subproblems. Before calculating, you check a Dictionary or Array (the memo table) to see if you've already solved it. If yes, return the cached result. This is easy to write but can hit the recursion stack limit.

2. Tabulation (Bottom-Up)

Tabulation is "Iterative + Filling a Table." You start by solving the smallest subproblems first and use their results to solve larger ones. This is usually faster and more memory-efficient because it avoids recursion overhead.

4. Interview Mastery

Q: "When should I use DP instead of Recursion?"

Architect Answer: "You use DP when you notice that the same work is being repeated millions of times. For example, in a raw recursive Fibonacci(50), you calculate Fibonacci(2) billions of times. With DP, you calculate Fibonacci(2) exactly **once**. This turns an exponential O(2^N) algorithm into a linear O(N) algorithm. This leap in performance is why DP is a favorite topic in senior level interviews."